基数排序的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. public static int[] radixSort(int[] arr) { 
  27.     // 查找数组最大值 
  28.     int max = arr[0]; 
  29.     for (int i = 0; i < arr.length; i++) { 
  30.         max = Math.max(arr[i], max); 
  31.     } 
  32.     // 按位排序 
  33.     int digit = 1; 
  34.     for (int i = 1; i < max; digit*=10, i = digit) { 
  35.         arr = countingSort(arr, digit); 
  36.     } 
  37.     return arr; 

排序验证:

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

验证排序结果:

  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)); 

排序前:[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. private static int charAt(String s, int d) { 
  37.     if (d < s.length()) { 
  38.         return s.charAt(d); 
  39.     } 
  40.     return -1; 
  41. public static void exch(String[] arr, int sourceIdx, int targetIdx) { 
  42.     String tmp = arr[sourceIdx]; 
  43.     arr[sourceIdx] = arr[targetIdx]; 
  44.     arr[targetIdx] = tmp; 
  45. 结果验证: 
  46.  
  47.  public static void main(String[] args) { 
  48.      String[] a = new String[]{"by","air","she","shell","the","okay","bump","shirt","shells","sh","the","shells","the"}; 
  49.      System.out.println("排序前:" + JSON.toJSONString(a)); 
  50.      sortStr(a, 0, a.length - 1, 0); 
  51.      System.out.println("排序后:" + JSON.toJSONString(a)); 
  52.  } 

排序前:["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/