排序--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[][]bucket=newint[10][arr.length];//为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数//可以这里理解//比如：bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数int[]bucketElementCounts=newint[10];//第1轮(针对每个元素的个位进行排序处理)for(intj=0;j<arr.length;j++){//取出每个元素的个位的值intdigitOfElement=arr[j]/1%10;//放入到对应的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];bucketElementCounts[digitOfElement]++;}//按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)intindex=0;//遍历每一桶，并将桶中是数据，放入到原数组for(intk=0;k<bucketElementCounts.length;k++){//如果桶中，有数据，我们才放入到原数组if(bucketElementCounts[k]!=0){//循环该桶即第k个桶(即第k个一维数组), 放入for(intl=0;l<bucketElementCounts[k];l++){//取出元素放入到arrarr[index++]=bucket[k][l];}}//第l轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！bucketElementCounts[k]=0;}System.out.println("第1轮，对个位的排序处理 arr ="+Arrays.toString(arr));//==========================================//第2轮(针对每个元素的十位进行排序处理)for(intj=0;j<arr.length;j++){// 取出每个元素的十位的值intdigitOfElement=arr[j]/10%10;//748 / 10 => 74 % 10 => 4// 放入到对应的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];bucketElementCounts[digitOfElement]++;}// 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)index=0;// 遍历每一桶，并将桶中是数据，放入到原数组for(intk=0;k<bucketElementCounts.length;k++){// 如果桶中，有数据，我们才放入到原数组if(bucketElementCounts[k]!=0){// 循环该桶即第k个桶(即第k个一维数组), 放入for(intl=0;l<bucketElementCounts[k];l++){// 取出元素放入到arrarr[index++]=bucket[k][l];}}//第2轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！bucketElementCounts[k]=0;}System.out.println("第2轮，对个位的排序处理 arr ="+Arrays.toString(arr));//第3轮(针对每个元素的百位进行排序处理)for(intj=0;j<arr.length;j++){// 取出每个元素的百位的值intdigitOfElement=arr[j]/100%10;// 748 / 100 => 7 % 10 = 7// 放入到对应的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];bucketElementCounts[digitOfElement]++;}// 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)index=0;// 遍历每一桶，并将桶中是数据，放入到原数组for(intk=0;k<bucketElementCounts.length;k++){// 如果桶中，有数据，我们才放入到原数组if(bucketElementCounts[k]!=0){// 循环该桶即第k个桶(即第k个一维数组), 放入for(intl=0;l<bucketElementCounts[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. 得到数组中最大的数的位数intmax=arr[0];//假设第一数就是最大数for(inti=1;i<arr.length;i++){if(arr[i]>max){max=arr[i];}}//得到最大数是几位数intmaxLength=(max+"").length();//定义一个二维数组，表示10个桶, 每个桶就是一个一维数组//说明//1. 二维数组包含10个一维数组//2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length//3. 名明确，基数排序是使用空间换时间的经典算法int[][]bucket=newint[10][arr.length];//为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数//可以这里理解//比如：bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数int[]bucketElementCounts=newint[10];//这里我们使用循环将代码处理for(inti=0,n=1;i<maxLength;i++,n*=10){//(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位..for(intj=0;j<arr.length;j++){//取出每个元素的对应位的值intdigitOfElement=arr[j]/n%10;//放入到对应的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];bucketElementCounts[digitOfElement]++;}//按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)intindex=0;//遍历每一桶，并将桶中是数据，放入到原数组for(intk=0;k<bucketElementCounts.length;k++){//如果桶中，有数据，我们才放入到原数组if(bucketElementCounts[k]!=0){//循环该桶即第k个桶(即第k个一维数组), 放入for(intl=0;l<bucketElementCounts[k];l++){//取出元素放入到arrarr[index++]=bucket[k][l];}}//第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！bucketElementCounts[k]=0;}System.out.println("第"+(i+1)+"轮，对个位的排序处理 arr ="+Arrays.toString(arr));}}}

得到最大数是几位数
int maxLength = (max + “”).length();

代码实现 2

确认最大数的位数后,没轮排序,又用到计数排序的原理

importjava.util.Arrays;publicclassMultiKeyRadixSort{publicstaticvoidradixSort(int[]data){System.out.println("开始排序：");//1. 得到数组中最大的数的位数intmax=data[0];//假设第一数就是最大数for(inti=1;i<data.length;i++){if(data[i]>max){max=data[i];}}//得到最大数是几位数intmaxLength=(max+"").length();//待排序数组的长度intarrayLength=data.length;int[]temp=newint[arrayLength];int[]buckets=newint[10];for(inti=0,rate=1;i<maxLength;i++){// 重置count数组，开始统计第二个关键字Arrays.fill(buckets,0);// 当data数组的元素复制到temp数组中进行缓存System.arraycopy(data,0,temp,0,arrayLength);for(intj=0;j<arrayLength;j++){intsubKey=(temp[j]/rate)%10;buckets[subKey]++;}for(intj=1;j<10;j++){buckets[j]=buckets[j]+buckets[j-1];}for(intm=arrayLength-1;m>=0;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("排序之前：\n"+java.util.Arrays.toString(data));radixSort(data);System.out.println("排序之后：\n"+java.util.Arrays.toString(data));}}

注意: --buckets[index] 会改变数组中的值

publicclassTest01{publicstaticvoidmain(String[]args){int[]buckets=newint[]{1,2,3};System.out.println(Arrays.toString(buckets));for(inti=0;i<buckets.length;i++){inta=--buckets[i];System.out.println("a= "+a);System.out.println("=========");}System.out.println(Arrays.toString(buckets));}}