好程序员Java学习路线分享5分钟了解基数排序-创新互联

好程序员Java学习路线分享5分钟了解基数排序，前言：基数排序无需进行比较和交换，而是利用分配和收集两种基本操作实现排序。基数排序分为两种：第一种是LSD ，从最低位开始排序；第二种是 MSD， 从最高位开始排序。

基数排序思想介绍

分配：对于数字，每位的取值范围是0-9，因此需要10个容器（我们可以将其称为桶），这10个桶标号为0-9。每趟排序时，我们取每一个元素在该位的数值依次放入桶中。

2. 收集：在一趟排序完成后，我们按顺序从0-9的桶中依次取元素。

3. 继续进行分配和收集，直到大位数排序完成。

算法说明：

待排序数据：12, 34, 2, 123, 25, 59, 37

采用LSD，从低位开始排序

第一轮：取个位数，放入对应的桶，比如12的个位数是2，放到2号桶；34的个位数是4，放到4号桶

第一轮后，得到数据：12, 2, 123, 34, 25, 37, 59

第二轮：取十位数，放入桶中。比如2，十位数是0，放到0号桶

第二轮后，得到数据：2, 12, 123, 25, 34, 37, 59

第三轮：取百位数，放入桶

最后，得到有序数据 2, 12, 25, 34, 37, 59, 123

基数排序的代码实现

private static void radixSort(int[] arr) {
//存储大值，暂时记录为第一个元素
int max = arr[0];
//获取待排序数组中的大值
for (int v : arr) {
if (v > max) {
max = v;
}
}
// 用列表表示桶，一共10个桶，每个桶对应的元素也是列表
List> list = new ArrayList>();
for(int i = 0; i < 10; i ++) {
list.add(new ArrayList());
}
// 确定循环轮数
for(int i = 0, factor = 1; i < max; factor *= 10, i ++) {
for(int j = 0; j < arr.length; j ++) {
// 根据相应的位（个位/十位...）取通号，然后将数据放入桶中
list.get((arr[j] / factor) % 10).add(arr[j]);
}
// 遍历桶，将其中数据放入arr数组中
for(int j = 0, k = 0; j < list.size(); j ++) {
while(!list.get(j).isEmpty()) {
arr[k] = list.get(j).get(0);
list.get(j).remove(0);
k++;
}
}
}
}

总结

基数排序是一种按记录关键字的各位值逐步进行排序的方法。一般适用于记录的关键字为整数类型的情况，对于字符串和文字排序不适合。

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。