基数排序(Redix Sort)
[toc]
基数排序非常适合用于整数排序（尤其是非负整数）
1.思路
依次对个位数、十位数、百位数、千位数、万位数...进行排序（从低位到高位）
例子
原数组
[129,69,593,23,6,89,54,8]
对个位数排序后为
[593,23,54,126,6,8,69,89]
对十位数排序后为
[6,8,23,126,54,69,89,593]
对百位数排序后为
[6,8,23,54,69,89,126,583]达到有序
2.代码实现
2.1基于计数排序实现
class RedixSourt extends Sort<num> {
@override
sort() {
//找到最大值
int max = list[0];
for (var i = 1; i < list.length; i++) {
if (list[i]>max) {
max = list[i];
}
}
// 个位数: array[i] / 1 % 10 = 3
// 十位数：array[i] / 10 % 10 = 9
// 百位数：array[i] / 100 % 10 = 5
// 千位数：array[i] / 1000 % 10 = ...
for (var divider = 1; divider <= max; divider *=10) {
_countsort(divider);
}
}
///
/// Author: liyanjun
/// description: 每一轮采取计数排序
///
_countsort(int divider) {
//找到最大值和最小值
// int max = list[0];
// int min = max;
// for (var i = 1; i < list.length; i++) {
// if (list[i] > max) {
// max = list[i];
// }
// if (list[i] < min) {
// min = list[i];
// }
// }
//因为0~9 位数不多，可以认为就是0，9
//开辟控件，存储次数
List counts = List.filled(10, 0);
//统计每个整数出现的次数 list[i]的基数
for (var i = 0; i < list.length; i++) {
int no = list[i]~/divider % 10;
counts[no]++;
}
//累加次数
for (var i = 1; i < counts.length; i++) {
counts[i] += counts[i-1];
}
//倒序遍历数组，将它放到有序数组的合适位置
//得到元素k在有序数组的索引
List<int> newList = List(list.length);
for (var i = list.length - 1; i >= 0; i--) {
int no = list[i]~/divider % 10;
int k = no;//这里要统计基数的值
newList[--counts[k]] = list[i];
}
//将有序数组赋值给list
list = newList;
}
}
2.1.1复杂度分析
- 最好、最坏、平均时间复杂度：
，d 是最大值的位数，k 是进制,这里k是10。属于稳定排序
- 空间复杂度：O(n + k)，k 是进制
2.2 思路2
1.每一轮放进一个二维数组 [10][list.length]
2.比较基数位置的数字是多少，就放在哪一而数组
过程如图
如图所示
image.png
代码
sort() {
//找到最大值
int max = list[0];
for (var i = 1; i < list.length; i++) {
if (list[i] > max) {
max = list[i];
}
}
// 个位数: array[i] / 1 % 10 = 3
// 十位数：array[i] / 10 % 10 = 9
// 百位数：array[i] / 100 % 10 = 5
// 千位数：array[i] / 1000 % 10 = ...
/// 1.每一轮放进一个二维数组 [10][list.length]
/// 2.比较基数位置的数字是多少，就放在哪一而数组
//桶数组
List<List<int>> buckets = List.generate(10,(index) =>List.generate(list.length, (index) => 0));
//每个桶的元素数量，方便最后取值
List<int> bucketsSize = List.filled(buckets.length, 0);
for (var divider = 1; divider <= max; divider *= 10) {
for (var i = 0; i < list.length; i++) {
int no = list[i] ~/ divider % 10;
buckets[no][bucketsSize[no]++] = list[i];
}
int index = 0;
for (var i = 0; i < buckets.length; i++) {
for (var j = 0; j < bucketsSize[i]; j++) {
list[index++] = buckets[i][j];
}
bucketsSize[i] = 0;
}
}
}
2.2.1复杂度分析
空间复杂度是 O(kn + k) ，时间复杂度是 O(dn)
d 是最大值的位数，k 是进制
