常见排序算法总结 (二) - 不基于比较的排序

devtools/2024/11/27 0:40:29/

计数排序

算法思想

用哈希表记录每个不同元素出现的次数，然后再根据这个记录还原。

稳定性分析

计数排序是稳定的，如果待排序元素不是纯数值，那么用链地址法来解决冲突，遍历的过程中按链表元素的先后顺序还原元素就可以保证元素的相对位置不发生改变。

具体实现

public void countingSort(int[] arr) {// 查找数组中的最小最大值，确定映射范围int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;for(int item : arr) {min = Math.min(min, item);max = Math.max(max, item);}int range = max - min + 1;int[] count = new int[range];// 统计每个元素出现的次数for (int item : arr) {count[item - min]++; // 注意每个元素都要先映射后记录}// 改造成前缀分区的形式，方便快速地确定还原后的元素位置for (int i = 1; i < count.length; i++) {count[i] += count[i - 1];}// 还原数组元素int[] res = new int[arr.length];for (int i = arr.length - 1; i >= 0; i--) {int cur = arr[i];res[--count[cur - min]] = cur;}// 把结果回写到原数组中System.arraycopy(res, 0, arr, 0, arr.length);
}

基数排序

算法思想

将元素根据基数从低位到高位分别散列到不同的分区中，再依次收集，就可以得到有序序列。

稳定性分析

基数排序是稳定的，收集的过程中依次收集值相等的元素，就不会改变它们的相对位置。

具体实现

public void radixSort(int[] arr) {int base = 10; // 定义基数，基数可以在一定范围内修改，也许会影响性能int n = arr.length;int[] res = new int[n];// 根据最小值映射原数组，防止数组下标出现负数int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;for(int item : arr) {min = Math.min(min, item);}for(int i = 0; i < n; i++) {arr[i] -= min;max = Math.max(max, arr[i]);}// 根据最大值计算当前基数下最长数字的长度int bits = 0;while (max != 0) {bits++;max /= base;}int[] count = new int[base];// 最长的数字有多少位，就要重复收集多少次for (int offset = 1; bits > 0; offset *= base, bits--) {Arrays.fill(count, 0); // 避免脏数据导致 res 数组下标越界// 统计每个元素出现的次数for (int item : arr) {// 注意这个偏移的写法，在元素本身不可更改的情况下很好用count[(item / offset) % base]++;}// 改造成前缀分区的形式，方便快速地确定还原后的元素位置for (int i = 1; i < base; i++) {count[i] += count[i - 1];}// 还原数组元素for (int i = n - 1; i >= 0; i--) {res[--count[(arr[i] / offset) % base]] = arr[i];}// 把结果回写到原数组中System.arraycopy(res, 0, arr, 0, n);}// 把数组元素映射回来for (int i = 0; i < n; i++) {arr[i] += min;}
}

梳理总结

不基于比较的排序使用起来有限制，要求数组元素的数值范围有限。
上述两种算法>排序算法的效率很高，时间复杂度达到了 $O (N)$ ， $N$ 表示数组中元素的数量；同时也需要 $O (M)$ 的额外空间， $M$ 表示用到的哈希表长度。
计数排序和基数排序是有应用场景的，在某些算法题中，明确数组元素范围有限的情况下，手写的计数排序可以在排序这个步骤上提升效率。