排序--07---基数排序

基数排序定义:基数排序(radix sort) 属于分配式排序,又称为桶子法(bucket)或bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些桶中,达到排序的作用原理:将所有待比较数值统一为同样的数位长度数位较短的数前面补零。然后从最低位开始依次进行一次排序。 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。举例图文说明:将数组{ 53, 3, 542, 748, 14, 214};使用基数排序,进行升序排序代码实现1将数组{ 53, 3, 542, 748, 14, 214};使用基数排序,进行升序排序过程分析:首先按上图分析,分成3轮,过程推导第1轮(针对每个元素的个位进行排序处理)第2轮(针对每个元素的十位进行排序处理)第3轮(针对每个元素的百位进行排序处理)推导过程代码importjava.util.Arrays;publicclassRadixSort{publicstaticvoidmain(String[]args){intarr[]{53,3,542,748,14,214};System.out.println(基数排序后 Arrays.toString(arr));radixSort(arr);System.out.println(基数排序后 Arrays.toString(arr));}//基数排序方法publicstaticvoidradixSort(int[]arr){//定义一个二维数组表示10个桶, 每个桶就是一个一维数组//说明//1. 二维数组包含10个一维数组//2. 为了防止在放入数的时候数据溢出则每个一维数组(桶)大小定为arr.length//3. 名明确基数排序是使用空间换时间的经典算法int[][]bucketnewint[10][arr.length];//为了记录每个桶中实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数//可以这里理解//比如bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数int[]bucketElementCountsnewint[10];//第1轮(针对每个元素的个位进行排序处理)for(intj0;jarr.length;j){//取出每个元素的个位的值intdigitOfElementarr[j]/1%10;//放入到对应的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]]arr[j];bucketElementCounts[digitOfElement];}//按照这个桶的顺序(一维数组的下标依次取出数据放入原来数组)intindex0;//遍历每一桶并将桶中是数据放入到原数组for(intk0;kbucketElementCounts.length;k){//如果桶中有数据我们才放入到原数组if(bucketElementCounts[k]!0){//循环该桶即第k个桶(即第k个一维数组), 放入for(intl0;lbucketElementCounts[k];l){//取出元素放入到arrarr[index]bucket[k][l];}}//第l轮处理后需要将每个 bucketElementCounts[k] 0 bucketElementCounts[k]0;}System.out.println(第1轮对个位的排序处理 arr Arrays.toString(arr));////第2轮(针对每个元素的十位进行排序处理)for(intj0;jarr.length;j){// 取出每个元素的十位的值intdigitOfElementarr[j]/10%10;//748 / 10 74 % 10 4// 放入到对应的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]]arr[j];bucketElementCounts[digitOfElement];}// 按照这个桶的顺序(一维数组的下标依次取出数据放入原来数组)index0;// 遍历每一桶并将桶中是数据放入到原数组for(intk0;kbucketElementCounts.length;k){// 如果桶中有数据我们才放入到原数组if(bucketElementCounts[k]!0){// 循环该桶即第k个桶(即第k个一维数组), 放入for(intl0;lbucketElementCounts[k];l){// 取出元素放入到arrarr[index]bucket[k][l];}}//第2轮处理后需要将每个 bucketElementCounts[k] 0 bucketElementCounts[k]0;}System.out.println(第2轮对个位的排序处理 arr Arrays.toString(arr));//第3轮(针对每个元素的百位进行排序处理)for(intj0;jarr.length;j){// 取出每个元素的百位的值intdigitOfElementarr[j]/100%10;// 748 / 100 7 % 10 7// 放入到对应的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]]arr[j];bucketElementCounts[digitOfElement];}// 按照这个桶的顺序(一维数组的下标依次取出数据放入原来数组)index0;// 遍历每一桶并将桶中是数据放入到原数组for(intk0;kbucketElementCounts.length;k){// 如果桶中有数据我们才放入到原数组if(bucketElementCounts[k]!0){// 循环该桶即第k个桶(即第k个一维数组), 放入for(intl0;lbucketElementCounts[k];l){// 取出元素放入到arrarr[index]bucket[k][l];}}//第3轮处理后需要将每个 bucketElementCounts[k] 0 bucketElementCounts[k]0;}System.out.println(第3轮对个位的排序处理 arr Arrays.toString(arr));}}最终排序代码:importjava.util.Arrays;publicclassRadixSort01{publicstaticvoidmain(String[]args){intarr[]{53,3,542,748,14,214};System.out.println(基数排序后 Arrays.toString(arr));radixSort(arr);System.out.println(基数排序后 Arrays.toString(arr));}//基数排序方法publicstaticvoidradixSort(int[]arr){//根据前面的推导过程我们可以得到最终的基数排序代码//1. 得到数组中最大的数的位数intmaxarr[0];//假设第一数就是最大数for(inti1;iarr.length;i){if(arr[i]max){maxarr[i];}}//得到最大数是几位数intmaxLength(max).length();//定义一个二维数组表示10个桶, 每个桶就是一个一维数组//说明//1. 二维数组包含10个一维数组//2. 为了防止在放入数的时候数据溢出则每个一维数组(桶)大小定为arr.length//3. 名明确基数排序是使用空间换时间的经典算法int[][]bucketnewint[10][arr.length];//为了记录每个桶中实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数//可以这里理解//比如bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数int[]bucketElementCountsnewint[10];//这里我们使用循环将代码处理for(inti0,n1;imaxLength;i,n*10){//(针对每个元素的对应位进行排序处理) 第一次是个位第二次是十位第三次是百位..for(intj0;jarr.length;j){//取出每个元素的对应位的值intdigitOfElementarr[j]/n%10;//放入到对应的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]]arr[j];bucketElementCounts[digitOfElement];}//按照这个桶的顺序(一维数组的下标依次取出数据放入原来数组)intindex0;//遍历每一桶并将桶中是数据放入到原数组for(intk0;kbucketElementCounts.length;k){//如果桶中有数据我们才放入到原数组if(bucketElementCounts[k]!0){//循环该桶即第k个桶(即第k个一维数组), 放入for(intl0;lbucketElementCounts[k];l){//取出元素放入到arrarr[index]bucket[k][l];}}//第i1轮处理后需要将每个 bucketElementCounts[k] 0 bucketElementCounts[k]0;}System.out.println(第(i1)轮对个位的排序处理 arr Arrays.toString(arr));}}}得到最大数是几位数int maxLength (max “”).length();代码实现 2确认最大数的位数后,没轮排序,又用到计数排序的原理importjava.util.Arrays;publicclassMultiKeyRadixSort{publicstaticvoidradixSort(int[]data){System.out.println(开始排序);//1. 得到数组中最大的数的位数intmaxdata[0];//假设第一数就是最大数for(inti1;idata.length;i){if(data[i]max){maxdata[i];}}//得到最大数是几位数intmaxLength(max).length();//待排序数组的长度intarrayLengthdata.length;int[]tempnewint[arrayLength];int[]bucketsnewint[10];for(inti0,rate1;imaxLength;i){// 重置count数组开始统计第二个关键字Arrays.fill(buckets,0);// 当data数组的元素复制到temp数组中进行缓存System.arraycopy(data,0,temp,0,arrayLength);for(intj0;jarrayLength;j){intsubKey(temp[j]/rate)%10;buckets[subKey];}for(intj1;j10;j){buckets[j]buckets[j]buckets[j-1];}for(intmarrayLength-1;m0;m--){intsubKey(temp[m]/rate)%10;data[--buckets[subKey]]temp[m];}System.out.println(对rate位上子关键字排序java.util.Arrays.toString(data));rate*10;}}publicstaticvoidmain(String[]args){int[]data{1100,192,221,12,13};System.out.println(排序之前\njava.util.Arrays.toString(data));radixSort(data);System.out.println(排序之后\njava.util.Arrays.toString(data));}}注意: --buckets[index] 会改变数组中的值publicclassTest01{publicstaticvoidmain(String[]args){int[]bucketsnewint[]{1,2,3};System.out.println(Arrays.toString(buckets));for(inti0;ibuckets.length;i){inta--buckets[i];System.out.println(a a);System.out.println();}System.out.println(Arrays.toString(buckets));}}基数排序总结:基数排序是对传统桶排序的扩展速度很快基数排序是经典的空间换时间的方式占用内存很大当对海量数据排序时容易造OutOfMemoryError基数排序时稳定的有负数的数组我们不用基数排序来进行排序如果要支持负数参考:https://code.i-harness.com/zh-CN/q/e98fa9基数排序是经典的空间换时间的方法,占用内存很大.海量数据容易OOM算法分析最佳情况T(n) O(n * k)最差情况T(n) O(n * k)平均情况T(n) O(n * k) 稳定