-
介绍
基数排序法属于分配模式排序方式之一。它是按个位数、十位数、百位数、以此往上推来进行排序的，看看下边的演示就很容易明白怎么回事儿了。元素和元素之间不需要比较，这是它的神奇之处！ -
演示
代码如下：
private static void radixSort() {
int data[] = {60, 43, 802, 17, 3, 74, 22, 91, 105};
int i, j, k, n, m;
for (n = 1; n <= 100; n *= 10) {
int[][] tmp = new int[10][data.length]; // 都会存放在这个二维数组里
for (i = 0; i < data.length; i++) {
m = (data[i] / n) % 10;
tmp[m][i] = data[i]; //
}
k = 0;
for (i = 0; i < 10; i++) {
for (j = 0; j < data.length; j++) {
if (tmp[i][j] != 0) {
data[k] = tmp[i][j];
k++;
}
}
}
}
}
运行结果：
基数排序.png
- 分析
- 在所有情况下，时间复杂度均为O(n*log以p为底的k)；
- 是稳定排序法；
- 基数排序法会用到很大的额外空间来存放列表数据，其空间复杂度为O(n*p)；
- 若n很大，p固定或者很小，次排序法效率很高。
（n是原始数据的个数，p是数据字符数，k是原始数据的最大值）
