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

也想出现在这里？点击联系我~

基数排序

概念

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

2种排序方式

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

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

按位分割小技巧

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

LSD排序算法实现

算法思想

按位进行计数排序

算法实现代码

1. /**
2. *按位进行计数排序
3. *@paramarr
4. *@paramdivid
5. *@return
6. */
7. privatestaticint[]countingSort(int[]arr,intdivid){
9. int[]bucket=newint[10];
10. for(inti=0;i<arr.length;i++){
11. bucket[arr[i]/divid%10]++;
12. }
14. for(inti=1;i<bucket.length;i++){
15. bucket[i]=bucket[i-1]+bucket[i];
16. }
18. int[]sortArr=newint[arr.length];
19. for(inti=arr.length-1;i>=0;i–){
20. intposition=bucket[arr[i]/divid%10];
21. sortArr[position-1]=arr[i];
22. bucket[arr[i]/divid%10]–;
23. }
24. returnsortArr;
25. }
27. publicstaticint[]radixSort(int[]arr){
28. //查找数组最大值
29. intmax=arr[0];
30. for(inti=0;i<arr.length;i++){
31. max=Math.max(arr[i],max);
32. }
33. //按位排序
34. intdigit=1;
35. for(inti=1;i<max;digit*=10,i=digit){
36. arr=countingSort(arr,digit);
37. }
38. returnarr;
39. }

排序验证：

1. publicstaticvoidmain(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. publicstaticint[]sort(int[]arr){
3. intmax=arr[0];
4. for(inti=0;i<arr.length;i++){
5. //获取最大值
6. max=Math.max(arr[i],max);
7. }
9. //获取最大值的位数
10. intdigit=getDataDigit(max);
11. //计算最大值的基数
12. intradix=newDouble(Math.pow(10,digit-1)).intValue();
13. //msd基数排序
14. returnmsdSort(arr,radix);
15. }
17. /**
18. *MSD基数排序
19. *@paramarr
20. *@paramradix
21. *@return
22. */
23. publicstaticint[]msdSort(int[]arr,intradix){
25. //递归分组到个位，退出
26. if(radix<=0){
27. returnarr;
28. }
30. //分组计数器
31. int[]groupCounter=newint[10];
32. //分组桶
33. int[][]groupBucket=newint[10][arr.length];
34. //遍历待排序数组，按位分组
35. for(inti=0;i<arr.length;i++){
36. //计算分组桶位置
37. intposition=arr[i]/radix%10;
38. //将元素存入分组
39. groupBucket[position][groupCounter[position]]=arr[i];
40. //当前分组计数加1
41. groupCounter[position]++;
42. }
44. intindex=0;
45. int[]sortArr=newint[arr.length];
47. //遍历分组计数器
48. for(inti=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(intj=0;j<tmp.length;j++){
56. sortArr[index++]=tmp[j];
57. }
58. }elseif(groupCounter[i]==1){
59. //收集组内元素数量=1的元素
60. sortArr[index++]=groupBucket[i][0];
61. }
62. }
64. returnsortArr;
65. }
67. /**
68. *获取数据的位数
69. *@paramdata
70. *@return
71. */
72. publicstaticintgetDataDigit(intdata){
73. //intindex=0;
74. //intdigit=1;
75. //while(data/digit>0){
76. //digit*=10;
77. //index++;
78. //}
79. //returnindex;
81. returnString.valueOf(data).length();
82. }

验证排序结果：

1. publicstaticvoidmain(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. *@paramarr
7. *@paramlo
8. *@paramhi
9. *@paramd
10. */
11. publicstaticvoidsortStr(String[]arr,intlo,inthi,intd){
12. if(hi<=lo){
13. return;
14. }
15. //定义小于v的看门lt,大于v的看门gt
16. intlt=lo,gt=hi,i=lo+1,v=charAt(arr[lo],d);
17. while(i<=gt){
18. intt=charAt(arr[i],d);
19. if(t<v){
20. exch(arr,i++,lt++);
21. }elseif(t>v){
22. exch(arr,i,gt–);
23. }else{
24. i++;
25. }
26. }
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. privatestaticintcharAt(Strings,intd){
38. if(d<s.length()){
39. returns.charAt(d);
40. }
41. return-1;
42. }
43. publicstaticvoidexch(String[]arr,intsourceIdx,inttargetIdx){
44. Stringtmp=arr[sourceIdx];
45. arr[sourceIdx]=arr[targetIdx];
46. arr[targetIdx]=tmp;
47. }
48. 结果验证：
50. publicstaticvoidmain(String[]args){
51. String[]a=newString[]{"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"]

三种排序算法对比

总结

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

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