# 经典排序算法

计数排序,桶排序,基数排序

区别

  • 计数排序:每个桶只存储单一键值
  • 桶排序:每个桶存储一定范围的数值
  • 基数排序:根据键值的每位数字来分配桶

# 8. 计数排序

计数排序(Counting Sort)是一个非基于比较的排序算法,它的优势在于在对一定范围内的整数排序时,它的复杂度为 Ο(n + k),其中 k 是整数的范围,快于任何比较排序算法,当然这是一种牺牲空间换取时间的做法,例如下面两种就很适合计数排序

  • 一个县百万人的年龄排序
  • 高考几百万考生的成绩排序

而且当 O(k) > O(n log n) 的时候其效率反而不如基于比较的排序,基于比较的排序的时间复杂度在理论上的下限是 O(n log n),如归并,快速,堆排序

# 8.1. 算法步骤

图片

  • 找出待排序的数组中最大和最小的元素
  • 统计数组中每个值为 value 的元素出现的次数,存入数组 bucket 的第 value 项
  • 对所有的计数累加(从 bucket 中的第一个元素开始,每一项和前一项相加)
  • 反向填充目标数组:将每个元素 value 放在新数组的第 bucket(value) 项,每放一个元素就将 bucket(value) 减去 1

# 8.2. 基础版本

计数排序基础版本,使用最大值 + 1 计算需要几个 bucket,这样会导致最大值越大 bucket 数量越大,而且取数方式是不稳定的,也不支持负数

/**
 * 计数排序基础版本,不稳定,不支持负数
 * 使用最大值+1计算需要几个bucket
 *
 * 只用最大值计算这样会导致bucket过大浪费
 *
 * @param array
 */
private static void countingSort1(int[] array) {
    print(array);

    // 找到最大值计算需要几个bucket
    int maxValue = 0;
    for (int value : array) {
        if (maxValue < value) {
            maxValue = value;
        }
    }
    // 创建bucket
    int bucketLen = maxValue + 1;
    int[] bucket = new int[bucketLen];
    // 遍历数组,将值放入bucket中
    for (int value : array) {
        bucket[value]++;
    }
    // 输出bucket的值
    for (int i = 0, pos = 0; i < bucketLen; i++) {
        while (bucket[i] > 0) {
            array[pos] = i;
            pos++;
            bucket[i]--;
        }
    }

    System.out.println("bucketLen " + bucketLen);
    print(array);
}

给定个数组进行验证,可以看到排序成功

public static void main(String[] args) {
    int[] array = {5, 12, 10, 9, 6, 9, 7, 9, 9, 8, 5, 7, 8, 5, 6, 6, 6, 5, 7, 9, 8, 5, 15};
    System.out.println("---------- countingSort1 ----------");
    countingSort1(Arrays.copyOf(array, array.length));
}
---------- countingSort1 ----------
5 12 10 9 6 9 7 9 9 8 5 7 8 5 6 6 6 5 7 9 8 5 15 
bucketLen 16
5 5 5 5 5 6 6 6 6 7 7 7 8 8 8 9 9 9 9 9 10 12 15 

# 8.3. 优化版本

优化 bucket 数量大小,使用最大值和最小值计算极值差,支持负数,但是取数方式还是不稳定的

/**
 * 计数排序优化版本,不稳定,支持负数
 * 使用最大值和最小值计算极值差+1个bucket
 *
 * 可以看到bucket数量变小了
 * 存数时减去最小值,支持负数
 *
 * @param array
 */
private static void countingSort2(int[] array) {
    print(array);

    // 找到最大值和最小值计算需要几个bucket
    int maxValue = array[0], minValue = array[0];
    for (int value : array) {
        if (maxValue < value) {
            maxValue = value;
        } else if (minValue > value) {
            minValue = value;
        }
    }
    // 创建bucket
    int bucketLen = maxValue - minValue + 1;
    int[] bucket = new int[bucketLen];
    // 遍历数组,将值放入bucket中
    for (int value : array) {
        // 优化减小了bucket的大小
        int index = value - minValue;
        bucket[index]++;
        // bucket[value - minValue]++;
    }
    // print(bucket);
    // 输出bucket的值,按存取的方式取出元素
    for (int i = 0, pos = 0; i < bucket.length; i++) {
        // 根据bucket数组中存的次数去取排列好的元素
        while (bucket[i] > 0) {
            array[pos] = minValue + i;
            pos++;
            bucket[i]--;
        }
    }
}

给定个数组进行验证,可以看到 bucket 数量变小了

public static void main(String[] args) {
    int[] array2 = {5, 12, 10, 9, 6, 9, 7, 9, -9, -8, 5, 7, 8, 5, 6, 6, -6, -5, 7, 9, 8, 5, 15};
    System.out.println("---------- countingSort2 ----------");
    countingSort2(Arrays.copyOf(array2, array2.length));
}
---------- countingSort2 ----------
5 12 10 9 6 9 7 9 -9 -8 5 7 8 5 6 6 -6 -5 7 9 8 5 15 
bucketLen 25
-9 -8 -6 -5 5 5 5 5 6 6 6 7 7 7 8 8 9 9 9 9 10 12 15  

# 8.4. 优化版本v2

优化取数方式,利用累加数组做到算法稳定,只使用最大值,不支持负数

/**
 * 计数排序优化版本v2,利用累加数组做到算法稳定,不支持负数
 * 使用最大值计算需要几个bucket
 *
 * @param array
 */
private static void countingSort3(int[] array) {
    print(array);

    // 找到最大值计算需要几个bucket
    int maxValue = 0;
    for (int value : array) {
        if (maxValue < value) {
            maxValue = value;
        }
    }
    // 创建bucket
    int bucketLen = maxValue + 1;
    int[] bucket = new int[bucketLen];
    // 遍历数组,将值放入bucket中
    for (int value : array) {
        bucket[value]++;
    }

    print(bucket);

    int[] tempArray = new int[array.length];
    // 利用累加数组计算出元素下标
    for (int i = 1; i < bucket.length; i++) {
        bucket[i] = bucket[i] + bucket[i - 1];
    }

    print(bucket);

    // 利用累加数组的方式取出元素,从最后一位开始
    for (int i = array.length - 1; i >= 0; i--) {
        // 取出原数组每一位的值
        int value = array[i];
        // 将其-1后得到的就是它的在bucket中的下标
        bucket[value]--;
        // 根据bucket加下标得到该元素最终在有序数组中的下标
        int pos = bucket[value];
        // 赋值到新数组对应的下标位置
        tempArray[pos] = array[i];
    }

    System.out.println("bucketLen " + bucketLen);
    print(tempArray);
}

给定个数组进行验证,可以看到排序成功

public static void main(String[] args) {
    int[] array = {5, 12, 10, 9, 6, 9, 7, 9, 9, 8, 5, 7, 8, 5, 6, 6, 6, 5, 7, 9, 8, 5, 15};
    System.out.println("---------- countingSort3 ----------");
    countingSort3(Arrays.copyOf(array, array.length));
}
---------- countingSort3 ----------
5 12 10 9 6 9 7 9 9 8 5 7 8 5 6 6 6 5 7 9 8 5 15 
0 0 0 0 0 5 4 3 3 5 1 0 1 0 0 1 
0 0 0 0 0 5 9 12 15 20 21 21 22 22 22 23 
bucketLen 16
5 5 5 5 5 6 6 6 6 7 7 7 8 8 8 9 9 9 9 9 10 12 15 

# 8.5. 优化版本v3

优化 bucket 大小和取数方式,也支持负数,利用累加数组做到算法稳定

/**
 * 计数排序优化版本v3,利用累加数组做到算法稳定,支持负数
 * 使用最大值和最小值计算极值差+1个bucket
 * 存数时减去最小值,支持负数
 *
 * @param array
 */
private static void countingSort4(int[] array) {
    print(array);

    // 找到最大值和最小值计算需要几个bucket
    int maxValue = array[0], minValue = array[0];
    for (int value : array) {
        if (maxValue < value) {
            maxValue = value;
        } else if (minValue > value) {
            minValue = value;
        }
    }
    // 创建bucket
    int bucketLen = maxValue - minValue + 1;
    int[] bucket = new int[bucketLen];
    // 遍历数组,将值放入bucket中
    for (int value : array) {
        // 优化减小了bucket的大小
        int index = value - minValue;
        bucket[index]++;
        // bucket[value - minValue]++;
    }

    // print(bucket);

    int[] tempArray = new int[array.length];
    // 利用累加数组计算出元素下标
    for (int i = 1; i < bucket.length; i++) {
        bucket[i] = bucket[i] + bucket[i - 1];
    }

    // print(bucket);

    // 利用累加数组的方式取出元素,从最后一位开始
    for (int i = array.length - 1; i >= 0; i--) {
        // 取出原数组每一位的值
        int value = array[i] - minValue;
        // 将其-1后得到的就是它的在bucket中的下标
        bucket[value]--;
        // 根据bucket加下标得到该元素最终在有序数组中的下标
        int pos = bucket[value];
        // 赋值到新数组对应的下标位置
        tempArray[pos] = array[i];
    }

    System.out.println("bucketLen " + bucketLen);
    // print(array);
    print(tempArray);
}

给定个数组进行验证,可以看到排序成功

public static void main(String[] args) {
    int[] array2 = {5, 12, 10, 9, 6, 9, 7, 9, -9, -8, 5, 7, 8, 5, 6, 6, -6, -5, 7, 9, 8, 5, 15};
    System.out.println("---------- countingSort4 ----------");
    countingSort4(Arrays.copyOf(array2, array2.length));
}
---------- countingSort4 ----------
5 12 10 9 6 9 7 9 -9 -8 5 7 8 5 6 6 -6 -5 7 9 8 5 15 
bucketLen 25
-9 -8 -6 -5 5 5 5 5 6 6 6 7 7 7 8 8 9 9 9 9 10 12 15  

# 8.6. 算法总结

局限性

  • 当待排序序列的最大值和最小值差值特别大时,不适合使用计数排序算法
  • 当待排序序列的值不是整数时,不适合使用计数排序算法

适用于存储数的数据范围很小的情况下,快于任何比较排序算法,以空间换取时间

  • 描述
    • 统计小于等于该元素值的元素个数 i,于是该元素就放在目标数组的索引 i 位(i > 0)
  • 稳定性
    • 稳定的
  • 时间复杂度
    • 最好是 O(n + k)
    • 最差为 O(n + k)
    • 所以平均复杂度为 O(n + k)
  • 空间复杂度
    • 占用额外空间,为 O(k)

# 9. 桶排序

桶排序(Bucket Sort)是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,我们需要做到这两点

  • 在额外空间充足的情况下,尽量增大桶的数量
  • 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要,也影响到是否稳定

  • 当输入的数据可以均匀的分配到每一个桶中速度最快
  • 当输入的数据被分配到了同一个桶中速度最慢

# 9.1. 算法步骤

元素分布在桶中

图片

然后,元素在每个桶中排序

图片

桶排序核心思想就是将要排序的数据分到几个有序的桶里,在每个桶分别进行排序,每个桶排序完成后再把每个桶里的数据按照顺序依次取出,组成新的序列,该序列就是排好序的序列,类似归并排序中的分治思想

  • 设置一个定量的数组当作空桶
  • 遍历输入数据,并且把数据一个一个放到对应的桶里去
  • 对每个不是空的桶进行排序
  • 从不是空的桶里把排好序的数据拼接起来

# 9.2. 基础版本

桶排序基础版本,使用数组实现,指定bucketSize为5

/**
 * 桶排序基础版本,使用数组实现,指定bucketSize为5
 * 存数时减去最小值,支持负数
 *
 * @param array
 */
private static void bucketSort1(int[] array) {
    print(array);

    int bucketSize = 5;
    int minValue = array[0];
    int maxValue = array[0];
    for (int value : array) {
        if (value < minValue) {
            minValue = value;
        } else if (value > maxValue) {
            maxValue = value;
        }
    }

    int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
    int[][] buckets = new int[bucketCount][0];

    // 利用映射函数将数据分配到各个桶中
    for (int i = 0; i < array.length; i++) {
        int index = (int) Math.floor((array[i] - minValue) / bucketSize);
        buckets[index] = arrAppend(buckets[index], array[i]);
    }

    int pos = 0;
    for (int[] bucket : buckets) {
        if (bucket.length <= 0) {
            continue;
        }
        // 对每个桶进行排序,这里使用了插入排序
        bucket = insertSort(bucket);
        for (int value : bucket) {
            array[pos] = value;
            pos++;
        }
    }

    print(array);
}

/**
 * 自动扩容,并保存数据
 *
 * @param array
 * @param value
 */
private static int[] arrAppend(int[] array, int value) {
    array = Arrays.copyOf(array, array.length + 1);
    array[array.length - 1] = value;
    return array;
}

/**
 * 插入排序
 *
 * @param array
 * @return
 */
private static int[] insertSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int current = array[i];
        int j = i;
        while (j > 0 && (current < array[j - 1])) {
            array[j] = array[j - 1];
            j--;
        }
        if (j != i) {
            array[j] = current;
        }
    }
    return array;
}

给定个数组进行验证,排序成功

public static void main(String[] args) {
    int[] array = {5, 12, 10, 9, 6, 9, 7, 9, -9, -8, 5, 7, 8, 5, 6, 6, -6, -5, 7, 9, 8, 5, 15};
    System.out.println("---------- bucketSort1 ----------");
    bucketSort1(Arrays.copyOf(array, array.length));
}
---------- bucketSort1 ----------
5 12 10 9 6 9 7 9 -9 -8 5 7 8 5 6 6 -6 -5 7 9 8 5 15 
-9 -8 -6 -5 5 5 5 5 6 6 6 7 7 7 8 8 9 9 9 9 10 12 15 

# 9.3. ArrayList实现

桶排序使用ArrayList实现,ArrayList支持负数存取,指定bucketSize为5

/**
 * 桶排序使用ArrayList实现,指定bucketSize为5
 * ArrayList支持负数存取
 * 
 * @param array
 */
private static void bucketSort2(int[] array) {
    print(array);

    int bucketSize = 5;
    List[] buckets = new ArrayList[bucketSize];
    // 初始化
    for (int i = 0; i < buckets.length; i++) {
        buckets[i] = new ArrayList<Integer>();
    }
    // 将待排序序列放入对应桶中
    for (int i = 0; i < array.length; i++) {
        // 计算对应的桶号
        int index = array[i] / 10;
        buckets[index].add(array[i]);
    }
    // 排序输出
    for (int k = 0, pos = 0; k < buckets.length; k++) {
        // 每个桶内进行排序
        buckets[k].sort(null);
        for (int j = 0; j < buckets[k].size(); j++) {
            array[pos] = (int) buckets[k].get(j);
            pos++;
        }
    }

    print(array);
}

给定个数组进行验证,排序成功

public static void main(String[] args) {
    int[] array = {5, 12, 10, 9, 6, 9, 7, 9, -9, -8, 5, 7, 8, 5, 6, 6, -6, -5, 7, 9, 8, 5, 15};
    System.out.println("---------- bucketSort2 ----------");
    bucketSort2(Arrays.copyOf(array, array.length));
}
---------- bucketSort2 ----------
5 12 10 9 6 9 7 9 -9 -8 5 7 8 5 6 6 -6 -5 7 9 8 5 15 
-9 -8 -6 -5 5 5 5 5 6 6 6 7 7 7 8 8 9 9 9 9 10 12 15 

# 9.4. 算法总结

局限性

桶排序不像常规排序那样没有限制,桶排序有相当的限制。因为桶的个数和大小都是我们人为设置的,而每个桶又要避免空桶的情况,所以我们在使用桶排序的时候即需要排序数列要求偏均匀,又要要求桶的设计兼顾效率和空间,和计数排序一样,当待排序序列的最大值和最小值差值特别大时,也不适合使用桶排序,不然会造成很大的空间浪费

  • 描述
    • 将值为 i 的元素放入 i 号桶,将桶内元素排序,最后依次把桶里的元素倒出来
  • 稳定性
    • 一般是稳定的,当桶内排序使用不稳定算法,才会导致不稳定
  • 时间复杂度
    • 最好是 O(n + k)
    • 最差为 O(n^2)
    • 所以平均复杂度为 O(n + k)
  • 空间复杂度
    • 占用额外空间,为 O(n + k)

# 10. 基数排序

基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数

基数排序有两种排序方法

  • 最高位优先法(Most Significant Digit first),简称 MSD 法
  • 最低位优先法(Least Significant Digit first),简称 LSD 法

最高位优先法(MSD)

简单来说就是从高位开始,先按 k1 排序分组,同一组中记录,关键码 k1 相等,再对各组按 k2 排序分成子组之后,对后面的关键码继续这样的排序分组,直到按最次位关键码 kd 对各子组排序后,再将各组连接起来,便得到一个有序序列

最低位优先法(LSD)

简单来说就是从低位开始,先从 kd 开始排序,再对 kd - 1 进行排序,依次重复,直到对 k1 排序后便得到一个有序序列

# 10.1. 算法步骤

(LSD)动图演示

图片

(LSD)算法步骤

  • 取得数组中的最大数,并取得位数
  • 位数较短的通过补 0 达到长度一致
  • arr 为原始数组,从最低位开始取每个位组成 radix 数组;
  • 对 radix 进行计数排序
  • 重复每位数进行排序后,再将各组连接起来,便得到一个有序序列

# 10.2. 基础版本

/**
 * 基数排序基础版本,不支持负数
 *
 * @param array
 */
private static void radixSort1(int[] array) {
    print(array);

    int[] tempArray = new int[array.length];
    int[] counter = new int[10];

    // 使用最大值计算位数
    int maxValue = array[0];
    for (int value : array) {
        if (maxValue < value) {
            maxValue = value;
        }
    }
    // 获取位数
    int maxDigit = getNumLength(maxValue);
    for (int i = 0; i < maxDigit; i++) {
        int division = (int) Math.pow(10, i);
        // System.out.println(division);

        for (int j = 0; j < array.length; j++) {
            int num = array[j] / division % 10;
            counter[num]++;
        }

        // 累加数组保证稳定
        for (int m = 1; m < counter.length; m++) {
            counter[m] = counter[m] + counter[m - 1];
        }

        // 利用累加数组的方式取出元素,从最后一位开始
        for (int n = array.length - 1; n >= 0; n--) {
            // 取出所在counter下标
            int num = array[n] / division % 10;
            // 将其-1后得到的就是它的在counter中的下标
            counter[num]--;
            // 根据counter加下标得到该元素最终在有序数组中的下标
            int pos = counter[num];
            // 赋值到新数组对应的下标位置
            tempArray[pos] = array[n];
        }

        // 将tempArray复制到array
        // System.arraycopy(tempArray, 0, array, 0, array.length);
        array = Arrays.copyOf(tempArray, tempArray.length);
        // 将counter数组值全部填充置为0,重新开始下一轮
        Arrays.fill(counter, 0);

        print(array);
    }

    // print(array);
}

/**
 * 获取数字位数
 *
 * @param num
 * @return
 */
private static int getNumLength(long num) {
    if (num == 0) {
        return 1;
    }
    int length = 0;
    for (long temp = num; temp != 0; temp /= 10) {
        length++;
    }
    return length;
}

给定个数组进行验证,可以看到进行了 4 趟排序

  • 第 1 趟按个位数,将个位数的先排序好
  • 第 2 趟按十位数,再将十位数的排序好
  • 然后百位数,位数较短的缺失的位数默认为 0,原来的个位和十位数就按顺序到前面去了
  • 千位数也是一样,最终排序成功
public static void main(String[] args) {
    int[] array = {5, 122, 102, 95, 63, 70, 88, 73, 88, 81, 555, 666, 729, 19, 28, 45, 1115};
    System.out.println("---------- radixSort1 ----------");
    radixSort1(Arrays.copyOf(array, array.length));
}
---------- radixSort1 ----------
5 122 102 95 63 70 88 73 88 81 555 666 729 19 28 45 1115 
70 81 122 102 63 73 5 95 555 45 1115 666 88 88 28 729 19 
102 5 1115 19 122 28 729 45 555 63 666 70 73 81 88 88 95 
5 19 28 45 63 70 73 81 88 88 95 102 1115 122 555 666 729 
5 19 28 45 63 70 73 81 88 88 95 102 122 555 666 729 1115 

# 10.3. 优化版本

考虑负数的情况,扩展一倍队列数,其中 [0-9] 对应负数,[10-19] 对应正数(bucket + 10)

/**
 * 基数排序优化版本,支持负数
 *
 * 考虑负数的情况,扩展一倍队列数
 * 其中[0-9]对应负数,[10-19]对应正数(bucket + 10)
 *
 * @param array
 */
private static void radixSort2(int[] array) {
    print(array);

    int[] tempArray = new int[array.length];
    // 考虑负数的情况,扩展一倍队列数,其中[0-9]对应负数,[10-19]对应正数(bucket + 10)
    int[] counter = new int[20];

    // 使用最大值计算位数
    int maxValue = array[0];
    for (int value : array) {
        if (maxValue < value) {
            maxValue = value;
        }
    }
    // 获取位数
    int maxDigit = getNumLength(maxValue);
    for (int i = 0; i < maxDigit; i++) {
        int division = (int) Math.pow(10, i);
        // System.out.println(division);

        for (int j = 0; j < array.length; j++) {
            int num = array[j] / division % 10;
            // 值大于等于0,存放在10-19的正数区域
            // 其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)
            num = num + 10;
            counter[num]++;
        }

        // 累加数组保证稳定
        for (int m = 1; m < counter.length; m++) {
            counter[m] = counter[m] + counter[m - 1];
        }

        // 利用累加数组的方式取出元素,从最后一位开始
        for (int n = array.length - 1; n >= 0; n--) {
            // 取出所在counter下标
            int num = array[n] / division % 10;
            // 值大于等于0,存放在10-19的正数区域
            // 其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)
            num = num + 10;
            // 将其-1后得到的就是它的在counter中的下标
            counter[num]--;
            // 根据counter加下标得到该元素最终在有序数组中的下标
            int pos = counter[num];
            // 赋值到新数组对应的下标位置
            tempArray[pos] = array[n];
        }

        // 将tempArray复制到array
        // System.arraycopy(tempArray, 0, array, 0, array.length);
        array = Arrays.copyOf(tempArray, tempArray.length);
        // 将counter数组值全部填充置为0,重新开始下一轮
        Arrays.fill(counter, 0);

        print(array);
    }

    // print(array);
}

给定个带负数的数组进行验证,可以看到进行了 4 趟排序

  • 第 1 趟按个位数,将个位数的先排序好
  • 第 2 趟按十位数,再将十位数的排序好
  • 然后百位数,位数较短的缺失的位数默认为 0,原来的个位和十位数就按顺序到前面去了
  • 千位数也是一样,最终排序成功
public static void main(String[] args) {
    int[] array2 = {5, 122, 102, 95, 63, -7, 88, 73, 88, 81, -555, -666, 729, -19, 28, 45, 1115};
    System.out.println("---------- radixSort2 ----------");
    radixSort2(Arrays.copyOf(array2, array2.length));
}
---------- radixSort2 ----------
5 122 102 95 63 -7 88 73 88 81 -555 -666 729 -19 28 45 1115 
-19 -7 -666 -555 81 122 102 63 73 5 95 45 1115 88 88 28 729 
-666 -555 -19 -7 102 5 1115 122 28 729 45 63 73 81 88 88 95 
-666 -555 -19 -7 5 28 45 63 73 81 88 88 95 102 1115 122 729 
-666 -555 -19 -7 5 28 45 63 73 81 88 88 95 102 122 729 1115

# 10.3. 优化版本v2

使用二维数组实现

/**
 * 基数排序优化版本v2,使用二维数组实现,支持负数
 *
 * @param array
 */
private static void radixSort3(int[] array) {
    print(array);

    // 使用最大值计算位数
    int maxValue = array[0];
    for (int value : array) {
        if (maxValue < value) {
            maxValue = value;
        }
    }
    // 获取位数
    int maxDigit = getNumLength(maxValue);
    int mod = 10;
    int dev = 1;

    for (int i = 0; i < maxDigit; i++, dev = dev * 10, mod = mod * 10) {
        // 考虑负数的情况,扩展一倍队列数,其中[0-9]对应负数,[10-19]对应正数(bucket + 10)
        int[][] counter = new int[mod * 2][0];

        // 放入桶
        for (int j = 0; j < array.length; j++) {
            int bucket = ((array[j] % mod) / dev) + mod;
            counter[bucket] = arrayAppend(counter[bucket], array[j]);
        }

        // 稳定的,使用二维数组存放了值
        int pos = 0;
        for (int[] bucket : counter) {
            for (int value : bucket) {
                array[pos++] = value;
            }
        }

        print(array);
    }

    // print(array);
}

/**
 * 自动扩容,并保存数据
 *
 * @param arr
 * @param value
 */
private static int[] arrayAppend(int[] arr, int value) {
    arr = Arrays.copyOf(arr, arr.length + 1);
    arr[arr.length - 1] = value;
    return arr;
}

给定个带负数的数组进行验证,可以看到进行了 4 趟排序

  • 第 1 趟按个位数,将个位数的先排序好
  • 第 2 趟按十位数,再将十位数的排序好
  • 然后百位数,位数较短的缺失的位数默认为 0,原来的个位和十位数就按顺序到前面去了
  • 千位数也是一样,最终排序成功
public static void main(String[] args) {
    int[] array2 = {5, 122, 102, 95, 63, -7, 88, 73, 88, 81, -555, -666, 729, -19, 28, 45, 1115};
    System.out.println("---------- radixSort3 ----------");
    radixSort3(Arrays.copyOf(array2, array2.length));
}
---------- radixSort3 ----------
5 122 102 95 63 -7 88 73 88 81 -555 -666 729 -19 28 45 1115 
-19 -7 -666 -555 81 122 102 63 73 5 95 45 1115 88 88 28 729 
-666 -555 -19 -7 102 5 1115 122 28 729 45 63 73 81 88 88 95 
-666 -555 -19 -7 5 28 45 63 73 81 88 88 95 102 1115 122 729 
-666 -555 -19 -7 5 28 45 63 73 81 88 88 95 102 122 729 1115

# 10.4. 字符串排序

待补充

# 10.5. 算法总结

基数排序的性能比桶排序要略差,每一次关键字的桶分配都需要 O(n) 的时间复杂度,而且分配之后得到新的关键字序列又需要 O(n) 的时间复杂度

假如待排数据可以分为 k 个关键字,则基数排序的时间复杂度将是 O(2n * k) ,2 可以忽略,所以是 O(n * k),当然 k 要远远小于 n,因此基本上还是线性级别的

基数排序基于分别排序,分别收集,所以是稳定的,基数排序的空间复杂度为 O(n + k),其中 k 为桶的数量,一般来说 n >> k,因此额外空间需要大概 n 个左右

  • 描述
    • 一种多关键字的排序算法
  • 稳定性
    • 稳定的
  • 时间复杂度
    • 最好是 O(n * k)
    • 最差为 O(n * k)
    • 所以平均复杂度为 O(n * k)
  • 空间复杂度
    • 占用额外空间,为 O(n + k)

参考

上次更新时间: 2023-01-16 03:44:08