基数排序的1个小技巧，2种排序方式，3种排序算法

时间：2022-05-03 03:51:10

基数排序的1个小技巧，2种排序方式，3种排序算法

基数排序

基数排序的1个小技巧，2种排序方式，3种排序算法

概念

基数排序是非比较型整数排序算法，其原理是将整数按位分割进行排序。基数排序适用于大范围数据排序，打破了计数排序的限制。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数，所以基数排序也不是只能使用于整数。

2种排序方式

最低位优先法(LSD)：从最低位向最高位依次按位进行排序。

最高位优先法(MSD)：从最高位向最低位依次按位进行排序。

按位分割小技巧

arr[i] / digit % 10，其中digit为10^n。

LSD排序算法实现

算法思想

按位进行计数排序

算法实现代码

  1. /** 
  2.      * 按位进行计数排序 
  3.      * @param arr 
  4.      * @param divid 
  5.      * @return 
  6.      */ 
  7. private static int[] countingSort(int[] arr, int divid){ 
  8.  
  9.     int[] bucket = new int[10]; 
  10.     for (int i = 0; i < arr.length; i++) { 
  11.         bucket[arr[i] / divid % 10]++; 
  12.     } 
  13.  
  14.     for (int i = 1; i < bucket.length; i++) { 
  15.         bucket[i] = bucket[i-1] + bucket[i]; 
  16.     } 
  17.  
  18.     int[] sortArr = new int[arr.length]; 
  19.     for (int i = arr.length - 1; i >= 0; i--){ 
  20.         int position = bucket[arr[i] / divid % 10]; 
  21.         sortArr[position - 1] = arr[i]; 
  22.         bucket[arr[i] / divid % 10]--; 
  23.     } 
  24.     return sortArr; 
  25. } 
  26.  
  27. public static int[] radixSort(int[] arr) { 
  28.     // 查找数组最大值 
  29.     int max = arr[0]; 
  30.     for (int i = 0; i < arr.length; i++) { 
  31.         max = Math.max(arr[i], max); 
  32.     } 
  33.     // 按位排序 
  34.     int digit = 1; 
  35.     for (int i = 1; i < max; digit*=10, i = digit) { 
  36.         arr = countingSort(arr, digit); 
  37.     } 
  38.     return arr; 
  39. } 

排序验证：

  1. public static void main(String[] args) { 
  2.      int[] arr = {999,1000,1001,1000,999,1005}; 
  3.      System.out.println("排序前:" + JSON.toJSONString(arr)); 
  4.      int[] sortArr = radixSort(arr); 
  5.      System.out.println("排序后:" + JSON.toJSONString(sortArr)); 
  6.  } 

排序前:[999,1000,1001,1000,999,1005] 排序后:[999,999,1000,1000,1001,1005]

MSD排序算法实现

算法思想

从最高位开始，按位分组，当组内元素个数>1时，递归下一位分组，一直分到个位结束;收集元素个数=1的。

算法步骤

  • 查询最大值，获取最高位的基数。Math.pow(10, digit - 1)
  • 按位分组，存入桶内。groupBucket[position][groupCounter[position]] =arr[i];
  • 组内元素数量>1，下一位递归分组。if (groupBucket[i] > 1) {int[] tmp = msdSort(copyArr, radix / 10);}
  • 组内元素数量=1，收集元素。sortArr[index++] = groupBucket[i][0];

比如，对数组[333,1002,1001,1000,333,1003,2000]进行排序，操作步骤如下：

基数排序的1个小技巧，2种排序方式，3种排序算法

算法实现代码

  1. public static int[] sort(int[] arr){ 
  2.  
  3.     int max = arr[0]; 
  4.     for (int i = 0; i < arr.length; i++) { 
  5.         // 获取最大值 
  6.         max = Math.max(arr[i], max); 
  7.     } 
  8.  
  9.     // 获取最大值的位数 
  10.     int digit = getDataDigit(max); 
  11.     // 计算最大值的基数 
  12.     int radix = new Double(Math.pow(10, digit - 1)).intValue(); 
  13.     // msd基数排序 
  14.     return msdSort(arr, radix); 
  15. } 
  16.  
  17. /** 
  18.      * MSD 基数排序 
  19.      * @param arr 
  20.      * @param radix 
  21.      * @return 
  22.      */ 
  23. public static int[] msdSort(int[] arr, int radix){ 
  24.  
  25.     // 递归分组到个位，退出 
  26.     if (radix <= 0) { 
  27.         return arr; 
  28.     } 
  29.  
  30.     // 分组计数器 
  31.     int[] groupCounter = new int[10]; 
  32.     // 分组桶 
  33.     int[][] groupBucket = new int[10][arr.length]; 
  34.     // 遍历待排序数组，按位分组 
  35.     for (int i = 0; i < arr.length; i++) { 
  36.         // 计算分组桶位置 
  37.         int position = arr[i] / radix % 10; 
  38.         // 将元素存入分组 
  39.         groupBucket[position][groupCounter[position]] = arr[i]; 
  40.         // 当前分组计数加1 
  41.         groupCounter[position]++; 
  42.     } 
  43.  
  44.     int index = 0; 
  45.     int[] sortArr = new int[arr.length]; 
  46.  
  47.     // 遍历分组计数器 
  48.     for (int i = 0; i < groupCounter.length; i++) { 
  49.         // 组内元素数量>1，递归分组 
  50.         if (groupCounter[i] > 1) { 
  51.             int[] copyArr = Arrays.copyOf(groupBucket[i], groupCounter[i]); 
  52.             // 递归分组 
  53.             int[] tmp = msdSort(copyArr, radix / 10); 
  54.             // 收集递归分组后的元素 
  55.             for (int j = 0; j < tmp.length; j++) { 
  56.                 sortArr[index++] = tmp[j]; 
  57.             } 
  58.         } else if (groupCounter[i] == 1) { 
  59.             // 收集组内元素数量=1的元素 
  60.             sortArr[index++] = groupBucket[i][0]; 
  61.         } 
  62.     } 
  63.  
  64.     return sortArr; 
  65. } 
  66.  
  67. /** 
  68.      * 获取数据的位数 
  69.      * @param data 
  70.      * @return 
  71.      */ 
  72. public static int getDataDigit(int data) { 
  73.     //        int index = 0; 
  74.     //        int digit = 1; 
  75.     //        while (data / digit >0) { 
  76.     //            digit *= 10; 
  77.     //            index++; 
  78.     //        } 
  79.     //        return index; 
  80.  
  81.     return String.valueOf(data).length(); 
  82. } 

验证排序结果：

  1. public static void main(String[] args) { 
  2.     int[] arr = {333,1002,1001,1000,333,1003,2000}; 
  3.     System.out.println("排序前:" + JSON.toJSONString(arr)); 
  4.     int[] sortArr = sort(arr); 
  5.     System.out.println("排序后:" + JSON.toJSONString(sortArr)); 
  6. } 

排序前:[333,1002,1001,1000,333,1003,2000] 排序后:[333,333,1000,1001,1002,1003,2000]

三向切分字符快速排序

算法思想

按位将字符串切分为三个区间，小于v区间：[lo,lt-1]，等于v区间：[lt,gt]，大于v区间: [gt+1,hi]，依次递归三个区间。

算法步骤

  • 定义小于v区间的看门狗lt，大于v区间的看门狗gt。
  • 按位比较划分三个区间。
  • 递归三个区间。

算法实现代码

  1. /** 
  2.      * 按位将字符串切分为三个区间 
  3.      * 1. 小于v区间：[lo,lt] 
  4.      * 2. 等于v区间：[lt,gt] 
  5.      * 3. 大于v区间: [gt+1,hi] 
  6.      * @param arr 
  7.      * @param lo 
  8.      * @param hi 
  9.      * @param d 
  10.      */ 
  11. public static void sortStr(String[] arr, int lo, int hi, int d){ 
  12.     if (hi <= lo) { 
  13.         return; 
  14.     } 
  15.     // 定义小于v的看门lt, 大于v的看门gt 
  16.     int lt = lo, gt = hi, i = lo + 1, v = charAt(arr[lo],d); 
  17.     while (i <= gt){ 
  18.         int t = charAt(arr[i], d); 
  19.         if (t < v) { 
  20.             exch(arr, i++, lt++); 
  21.         } else if (t > v) { 
  22.             exch(arr, i, gt--); 
  23.         } else { 
  24.             i++; 
  25.         } 
  26.     } 
  27.  
  28.     // 递归小于v的区间 
  29.     sortStr(arr, lo, lt - 1, d); 
  30.     // 递归等于v的区间 
  31.     if (v >= 0) { 
  32.         sortStr(arr, lt, gt, d + 1); 
  33.     } 
  34.     // 递归大于v的区间 
  35.     sortStr(arr, gt + 1, hi, d); 
  36. } 
  37. private static int charAt(String s, int d) { 
  38.     if (d < s.length()) { 
  39.         return s.charAt(d); 
  40.     } 
  41.     return -1; 
  42. } 
  43. public static void exch(String[] arr, int sourceIdx, int targetIdx) { 
  44.     String tmp = arr[sourceIdx]; 
  45.     arr[sourceIdx] = arr[targetIdx]; 
  46.     arr[targetIdx] = tmp; 
  47. } 
  48. 结果验证： 
  49.  
  50.  public static void main(String[] args) { 
  51.      String[] a = new String[]{"by","air","she","shell","the","okay","bump","shirt","shells","sh","the","shells","the"}; 
  52.      System.out.println("排序前:" + JSON.toJSONString(a)); 
  53.      sortStr(a, 0, a.length - 1, 0); 
  54.      System.out.println("排序后:" + JSON.toJSONString(a)); 
  55.  } 

排序前:["by","air","she","shell","the","okay","bump","shirt","shells","sh","the","shells","the"] 排序后:["air","bump","by","okay","sh","she","shell","shells","shells","shirt","the","the","the"]

三种排序算法对比

算法

是否稳定

原地排序

运行时间

额外空间

优点领域

低位优先的字符串排序(LSD)

是

否

O(n x k)

O(n + k)

较短的定长字符串

高位优先的字符串排序(MSD)

是

否

O(n x k)

O(N+kk)

随机字符串

三向字符串快速排序

否

是

O(NlogN)

W+logN

通用排序算法，特别适用于含有较长公共前缀的字符串数组

总结

基数排序是稳定、非比较排序，适合用于大数据范围的。

原文链接：https://www.toutiao.com/i7002776272023683598/

标签：

相关文章