7.桶排+计数+基数
7. 桶排序
核心思想：将数组中元素分为几个有序的桶内，桶与桶之间是有序的，先对桶内的元素进行排序，这个桶内排序可以是之前用到的任意一个算法，为了降低时间复杂度可以选择快排或者归并排序，然后将桶内的元素依次取出
桶排序时间复杂度分析：
当桶的个数约等于元素个数的时候，时间复杂度接近线性时间复杂度O(n)
代码实现：
- 通过计算创建初始化几个桶，由于每个桶中的元素个数不确定，所以使用ArrayList数组来存放数据
- 将每个元素放到对应的桶中
- 对每个桶内的元素进行排序
- 从buckets中拿到排好序的数组
public class BucketSorter {
public void sort(int[] data){
if(data == null || data.length<2) return;
//1. 创建几个空的bucket
int maxValue = data[0];
for (int d : data) {
maxValue = Math.max(maxValue,d);
}
int bucketNum = maxValue / 10 +1; // 39/10+1 = 4
//使用动态数组来存储桶内的数据
ArrayList<Integer>[] buckets = new ArrayList[bucketNum];
//2. 将所有的元素添加到对应的bucket
for (int i = 0; i < data.length; i++) {
//计算当前元素应该被分配到哪一个桶里
int index = data[i] / 10;
if(buckets[index] == null){
buckets[index] = new ArrayList<>();
}
buckets[index].add(data[i]);
}
//3. 对每一个bucket中的元素进行排序
for (int i = 0; i < bucketNum; i++) {
ArrayList<Integer> bucketData = buckets[i];
if(bucketData != null){
new IntegerArrayQuickSorter().sort(bucketData);
}
}
//4. 从buckets中拿到排好序的数组
int index = 0;
for (int i = 0; i < bucketNum; i++) {
ArrayList<Integer> bucketData = buckets[i];
if(bucketData != null){
for (int j = 0; j < bucketData.size(); j++) {
data[index++] = bucketData.get(j);
}
}
}
}
}
桶排序的特点
- 空间复杂度是O(m)，m表示桶的个数，不是原地排序算法
- 桶排序是不是稳定算法取决于对桶内元素排序的算法
- 桶排序对数据要求非常苛刻：
- 桶与桶之间必须是有序的
- 待排序数据最好均匀的分配到每个桶中
桶排序应用—外部排序
外部排序就是对存储在磁盘中的数据进行排序，
外部排序的特点是：数据量比较大，内存有限，无法将数据全部加载到内存中
8. 计数排序
先对每一个分数进行计数，分数是0~5，六个元素，创建一个长度为6的数组，数组索引表示分数，元素值表示每个分数出现的次数
计数排序详细步骤
可以看作是特殊的桶排序，整个数组最大是5，最小是0，划分为6个桶，相同的元素都应该放到第一个桶内，但是由于桶内元素值都一样，没必要进行桶内排序，只需要记录桶里面出现了几次就可以了
省去了桶内排序的时间，应该如何计算每个分数在排序之后的位置？
-
对每个数据进行计数
-
计数累加（count中的数据从前向后累加）
-
计算每个分数存储的位置，初始化output数组，用于存放排好序的数组
定义一个指针i，从data数组最后一个开始
在count数组中定义一个指针j，在count中索引表示data中的分数
在output数组中有一个指针k，
count数组用来存放data数组中每个元素出现的次数，将得到的次数在count中进行计数累加，再新建一个output数组用来存放有序的元素，count数组中的数据此时就是data数组中数据在output数组中的元素下标
然后j需要–，i向前移动
j就需要移动到下标为3的位置
。。。
计数累加
计数排序中会生成count数组，count数组中的值为原始数组data中每个元素出现的次数，为什么在接下来的操作中要进行计数累加呢
在计数排序中，生成 count 数组后，进行计数累加的原因是为了确定每个元素在输出数组中的最终位置。以下是详细的解释：
- count
数组的作用：count[i] 表示原始数组 data 中元素值为 i 的出现次数。这个数组用于记录每个元素的频率。 - 累加过程的意义：
在对 count 数组进行累加的过程中，我们实际上是在将每个元素的出现次数累加到前面的元素上，以计算出每个元素在排序后应该放置的位置。这是因为在 count 数组中，count[i] 的值不仅表示 i 的出现次数，还表示所有小于或等于 i 的元素在原始数组中的总数。 - 如何理解：
- 假设 count[3] 是 4，这意味着数字 3 在原始数组中出现了 4 次。
- 如果在 count 数组中，count[2] 是 5，表示数字 2 和 3之前的数字（小于3）一共有 5 个。
- 累加后的 count 数组中，count[3] 就会变成 count[3] + count[2]，这表示所有出现小于或等于 3 的元素的总数。
- 这样，count[i] 的最终值就指明了排序后 i 应该放置在输出数组的哪个位置。
- 具体步骤：
通过累加，将每个 count[i] 表示为元素 i 在输出数组中最后的位置索引（如果考虑 0 索引，则是 count[i] - 1）。 - 在后续步骤中的应用：
在构建输出数组时，可以使用 count 中的累加值来确定元素的位置，并且每放置一个元素，就要将该元素的计数减一，以确保后续相同元素的正确位置。
总之，计数的累加是使得计数排序能够保持稳定性并确保每个元素可以被准确地放置在输出数组中的关键步骤。
代码：
public class CountSorter {
public void sort(int[] data){
if(data == null || data.length<=1) return;
//1.找到数组中最大值
int max = data[0];
for (int i = 0; i < data.length; i++) {
max = Math.max(max,data[i]);
}
//初始化计数器
int[] count = new int[max + 1];
//2.计数
for (int i = 0; i < data.length; i++) {
count[data[i]]++;
}
//3.计数累加
for (int i = 1; i < count.length; i++) {
count[i] += count[i-1];
}
//4.计算每个元素在排序数组中的位置
int[] output = new int[data.length];
for (int i = data.length-1; i>=0; i--) {
int j = data[i];
int k = count[j] - 1;
output[k] = data[i];
count[j]--;
}
//5.拷贝数组
for (int i = 0; i < data.length; i++) {
data[i] = output[i];
}
}
}
计数排序的特点
-
时间复杂度是O(n+k)，k表示数组元素最大范围
计数排序只能用在数据范围不大的场景中，如果数据范围k比排序的数据n大很多，就不适合用计数排序了
-
空间复杂度是O(n)，不是原地排序算法
-
是稳定的排序算法(i指针需要从data数组最后向前遍历，如果是顺序遍历会导致算法不稳定)
顺序遍历导致不稳定的情况：
考虑负数
public class CountingSorter {
public void sort(int[] data){
if(data == null || data.length<=1) return;
//1.找到数组中最大值
int max = data[0];
int min = data[0];
for (int i = 0; i < data.length; i++) { //O(n)
max = Math.max(max,data[i]);
min = Math.min(min,data[i]);
}
//初始化计数器
int[] count = new int[max - min + 1];
//2.计数
for (int i = 0; i < data.length; i++) { //O(n)
count[data[i] - min]++;
}
//3.计数累加
for (int i = 1; i < count.length; i++) { //O(k)
count[i] += count[i-1];
}
//4.计算每个元素在排序数组中的位置
int[] output = new int[data.length];
for (int i = data.length-1; i>=0; i--) { //O(n)
int j = data[i];
int k = count[j - min] - 1;
output[k] = data[i];
count[j - min]--;
}
//5.拷贝数组
for (int i = 0; i < data.length; i++) { //O(n)
data[i] = output[i];
}
}
public static void main(String[] args) {
int[] data = new int[]{12,23,36,9,24,42};
new CountingSorter().sort(data);
System.out.println(Arrays.toString(data));
}
}
9. 基数排序
核心思想：分别对每个元素的每一位进行排序
选择计数排序给基数排序的每位排序
//使用计数排序给数组中每个元素的某一位进行排序
private void countSort(int[] data){
//之所以是10，是因为数字只有0...9 十个数字
int[] count = new int[10];
//计数
for (int i = 0; i <data.length; i++) {
int digit = data[i]%10; //得到每个元素的个位数
count[digit]++;
}
//计数累加
for (int i = 1; i < 10; i++) {
count[i]+=count[i-1];
}
//计算每个元素在排序数组中的位置
int[] output = new int[data.length];
for (int i = data.length-1; i>=0; i--) {
int digit = data[i]%10;
int k = count[digit] -1;
output[k] = data[i];
count[digit]--;
}
for (int i = 0; i < data.length; i++) {
data[i] = output[i];
}
}
代码实现：
public class RadixSorter {
public void sort(int[] data){
if(data == null || data.length<=1) return;
//1.找到最大值
int max = data[0];
for (int i = 1; i < data.length; i++) {
max = Math.max(max,data[i]);
}
//2.对数组按照每个元素的每位进行计数排序
// 88
for(int exp = 1;max / exp>0;exp*=10){
countSort(data,exp);
}
}
//使用计数排序给数组中每个元素的某一位进行排序
private void countSort(int[] data,int exp){
//之所以是10，是因为数字只有0...9 十个数字
int[] count = new int[10];
//计数
for (int i = 0; i <data.length; i++) {
//个位数：(234 / 1) % 10 = 4
//十位数：(234 / 10) % 10 = 3
//百位数：(234 / 100) % 10 = 2
int digit = (data[i] / exp)%10; //得到每个元素的个位数
count[digit]++;
}
//计数累加
for (int i = 1; i < 10; i++) {
count[i]+=count[i-1];
}
//计算每个元素在排序数组中的位置
int[] output = new int[data.length];
for (int i = data.length-1; i>=0; i--) {
int digit = (data[i] / exp)%10;
int k = count[digit] -1;
output[k] = data[i];
count[digit]--;
}
for (int i = 0; i < data.length; i++) {
data[i] = output[i];
}
}
public static void main(String[] args) {
int[] data = new int[]{4512,4231,1923,2165,1141};
new RadixSorter().sort(data);
System.out.println(Arrays.toString(data));
}
}
基数排序的特点
- 时间复杂度：O(Cn)，C表示最大值的位数，可以省略
- 基数排序对要排序的数据是有要求的：
需要可以分割出来独立的“位”来比较，
而且每一位的数据范围不能太大，
要可以用线性算法来给每一位进行排序，否则基数排序的时间复杂度就无法做到O(n)了 - 空间复杂度：O(n)，不是原地排序算法
- 基数排序是稳定的排序算法