算法 - 基数排序（Radix Sort）

本文主要是介绍算法 - 基数排序（Radix Sort），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

基数排序非常适合用于整数排序（尤其是非负整数），因此只演示对非负整数进行基数排序
执行流程：一次对个位数、十位数、百位数、千位数、万位数…进行排序（从低位到高位）
个位数、十位数、百位数的取值范围都是固定的0~9，可以使用计数排序对它们进行排序
思考：如果先对高位排序，再对低位排序，是否可行？不行

实现

int max = array[0]; // 最大值
for (int i = 1; i < array.length; i++) {if (array[i] > max) max = array[i];
}
int[] output = new int[array.length];
int[] counts = new int[10];
for (int divider = 1; divider <= max; divider *=10) {// 对每一位进行计数排序coutingSort(divider, output, counts);
}

private void countingSort(int divider, int[] output, int[] counts) {for (int i = 0; i < counts.length; i++) {counts[i] = 0;}for (int i = 0; i < array.length; i++) {counts[array[i] / divider %10]++;}for (int i = 1; i < counts.length; i++) {counts[i] += counts[i - 1];}for (int i = array.length - 1; i >= 0; i--) {output[--counts[array[i] / divider %10]] = array[i];}for (int i = 0; i < array.length; i++) {array[i] = output[i];}
}

最好、最坏、平均时间复杂度：O(d*(n+k))，d是最大值的位数，k是进制。属于稳定排序
空间复杂度：O(n+k)，k是进制

另一种思路

在这里插入图片描述

int max = array[0]; // 最大值
for (int i = 1; i < array.length; i++) {if (array[i] > max) {max = array[i];}
}

// 桶数组
int[][] buckets = new int[10][array.length];
// 每个桶的元素数量
int[] bucketSizes = new int[buckets.length];
for(int divider = 1; divider <= max; divider *= 10) {for (int i = 0; i< array.length; i++) {int no = array[i] / divider % 10;buckets[no][bucketSizes[no]++] = array[i];}int index = 0;for (int i = 0; i < buckets.length; i++) {for (int j = 0; j< bucketSizes[i]; j++) {array[index++] = buckets[i][j];}bucketSizes[i] = 0;}
}