基数排序概念基数排序是一种非比较整数排序算法，其原理是按位划分对整数进行排序。基数排序适用于大规模数据排序，打破了计数排序的局限性。由于整数也可以表示特定格式的字符串（如姓名或日期）和浮点数，因此基数排序不限于整数。2排序方式最低位优先（LSD）：按位从最低位到最高位排序。Mostsignificantbitfirst(MSD)：按位从最高位到最低位排序。按位切分提示arr[i]/digit%10，其中digit为10^n。LSD排序算法实现算法思路计数排序算法实现代码按位bucket=newint[10];for(inti=0;i=0;i--){intposition=bucket[arr[i]/divid%10];sortArr[position-1]=arr[i];bucket[arr[i]/divid%10]--;}returnsortArr;}publicstaticint[]radixSort(int[]arr){//求数组的最大值intmax=arr[0];for(inti=0;i1时，递归分组下一位，直到单位位结束；收集元素个数=1的算法步数查询最大值，得到最高位的基数。Math.pow(10,digit-1)按数字分组并将它们存储在桶中。groupBucket[位置][groupCounter[位置]]=arr[i];分组中元素个数>1，递归分组下一位。if(groupBucket[i]>1){int[]tmp=msdSort(copyArr,radix/10);}group中元素个数=1，收集元素。sortArr[index++]=groupBucket[i][0];例如对数组[333,1002,1001,1000,333,1003,2000]进行排序，操作步骤如下：算法实现代码publicstaticint[]sort(int[]arr){intmax=arr[0];for(inti=0;i1，递归分组if(groupCounter[i]>1){int[]copyArr=Arrays.copyOf(groupBucket[i],groupCounter[i]);//递归分组int[]tmp=msdSort(copyArr,radix/10);//递归分组后收集元素for(intj=0;j0){//digit*=10;//index++;///returnindex;returnString.valueOf（数据）。length();}验证排序结果：publicstaticvoidmain(String[]args){int[]arr={333,1002,1001,1000,333,1003,2000};System.out.println("排序前："+JSON.toJSONString(arr));int[]sortArr=sort(arr);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]，递归按照三个区间算法步骤定义看门狗lt小于区间v，看门狗watchdog大于区间vdoordoggt.按位比较分为三个区间。递归三个区间。算法实现代码/***将字符串按bit*1分成三个区间。小于v区间：[lo,lt]*2。等于v区间：[lt,gt]*3。大于v区间：[gt+1,hi]*@paramarr*@paramlo*@paramhi*@paramd*/publicstaticvoidsortStr(String[]arr,intlo,inthi,intd){if(hi<=lo){return;}//定义小于v的gatekeeperlt,大于v的gatekeepergtintlt=lo,gt=hi,i=lo+1,v=charAt(arr[lo],d);while(i<=gt){intt=charAt(arr[i],d);if(tv){exch(arr,i,gt--);}else{i++;}}//递归小于v的范围sortStr(arr,lo,lt-1,d);//递归等于v的范围if(v>=0){sortStr(arr,lt,gt,d+1);}//递归范围大于vsortStr(arr,gt+1,hi,d);}privatestaticintcharAt(Strings,intd){if(d
