web开发中基数排序是什么意思

来源：恒创科技编辑：恒创科技编辑部

2024-01-31 23:01:59

这篇文章主要介绍了web开发中基数排序是什么意思，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

基数排序的例子

什么是基数排序呢？

考虑一下，虽然我们不能直接将所有范围内的数字都使用count数组进行排序，但是我们可以考虑按数字的位数来进行n轮count排序，每一轮都只对数字的某一位进行排序。

最终仍然可以得到结果，并且还可以摆脱count数组大小的限制，这就是基数排序。

假如我们现在数组的元素是：1221, 15, 20, 3681, 277, 5420, 71, 1522, 4793。

先看动画，看下最直观的基数排序的过程：

在上面的例子中，我们先对个位进行count排序，然后对十位进行count排序，然后是百位和千位。

最后生成最终的排序结果。

基数排序的java代码实现

因为基数排序实际上是分别按位数的count排序。所以我们可以重用之前写的count排序的代码，只是需要进行一些改造。

doCountingSort方法除了传入数组外，还需要传入排序的位数digit，我们用1，10，100，1000来表示。

看一下改造过后的doCountingSort方法：

publicvoiddoRadixSort(int[]array,intdigit){intn=array.length;//存储排序过后的数组intoutput[]=newint[n];//count数组，用来存储统计各个元素出现的次数intcount[]=newint[10];
Arrays.fill(count,0);
log.info("初始化count值:{}",count);//将原始数组中数据出现次数存入count数组for(inti=0;i<n;++i){
count[(array[i]/digit)%10]++;
}
log.info("count之后count值:{}",count);//这里是一个小技巧，我们根据count中元素出现的次数计算对应元素第一次应该出现在output中的下标。//这里的下标是从右往左数的for(inti=1;i<10;i++){
count[i]+=count[i-1];
}
log.info("整理count对应的output下标:{}",count);//根据count中的下标，构建排序后的数组//插入一个之后，相应的count下标要减一for(inti=n-1;i>=0;i--)
{
output[count[(array[i]/digit)%10]-1]=array[i];
count[(array[i]/digit)%10]--;
}
log.info("构建output之后的output值:{}",output);//将排序后的数组写回原数组for(inti=0;i<n;++i)
array[i]=output[i];
}

跟count排序变化不大，区别就是这里我们需要使用count[(array[i]/digit)%10]，来对每一位进行排序。

另外，为了计算出位数digit的值，我们还需要拿到数组中最大元素的值：

publicintgetMax(int[]array){intmx=array[0];for(inti=1;i<array.length;i++)if(array[i]>mx){
mx=array[i];
}returnmx;
}

看下怎么调用：

publicstaticvoidmain(String[]args){int[]array={1221,15,20,3681,277,5420,71,1522,4793};
RadixSortradixSort=newRadixSort();
log.info("radixSort之前的数组为:{}",array);//拿到数组的最大值，用于计算digitintmax=radixSort.getMax(array);//根据位数，遍历进行count排序for(intdigit=1;max/digit>0;digit*=10){
radixSort.doRadixSort(array,digit);
}
}

看下输出结果：

很好，结果都排序了。