Java编程技巧——数据结构与算法“基数排序”_0

基数排序基数排序（radixsort）属于“分布排序”，也叫“桶排序”或bin排序，顾名思义，它利用的是每一个的值键值的位，将待排序的元素分配到一定的桶中，达到排序的效果。基数排序是一种稳定性排序，基数排序方法是一种高效稳定的排序方法。基数排序是桶排序的扩展。基数排序是HermanHollis在1887年发明的，它的实现是这样的：把整数按照位数分成不同的数，然后根据每一位进行比较。排序的基本思想是将所有要比较的值统一为相同的位数长度，对位数较短的数进行零挂起。然后，从最低位开始，将它们一一排序。这样，完成从最低位到最高位的排序后，序列就变成了有序序列。代码案例包com.xie.sort；publicclassRadixSort{publicstaticvoidmain(String[]args){int[]arr=newint[8000000];for(inti=0;i<8000000;i++){arr[i]=(int)(Math.random()*800000000);}longstart=System.currentTimeMillis();radixSort(arr);longend=System.currentTimeMillis();System.out.println("耗时："+(end-start)+"ms");/*8万条数据，耗时：939ms*/}//基数排序publicstaticvoidradixSort(int[]arr){intmax=arr[0];for(inti=1;imax){max=arr[i];}}//数组中最长的位数intmaxLength=(max+"").length();//第一轮（对每个排序的单位位theelement)//定义一个二维数组，代表10个桶，每个桶是一个一维数组//1.二维数组包含10个一维数组//2。为了防止在输入数字时，如果数据溢出，将每个一维数组（桶）的大小设置为arr.length//3。基数排序是经典的以空间换时间的算法int[][]bucket=newint[10][arr.length];//为了记录每个桶中实际存储了多少数据，我们定义一个一维的数组来记录放入每个桶中的数据数量。//bucketElementCounts[0]，记录bucket[0]中的数据个数。int[]bucketElementCounts=newint[10];//按照桶的顺序（一维数组下标依次取出数据放入原数组）intindex=0;for(inti=0,n=10;i