[toc]
计数排序于1954年由Harold H. Seward提出，适合对一定范围内的整数进行排序
1.思路
统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引
2.实现
2.1 实现1
- 找出数组中最大的数字max
- 开辟一个长度为max+1的数组list1
- 数组的索引为数组中的数字，内容为该数字出现的次数
- 遍历list1,如果有值，则把索引存入目标数组，且list1该索引位置的值多少，目标数组存入数组几个
例如 数组为list=[7,3,5,8,6,7,4,5]，则开拍一个长度为位9的数组，内容
list[0]=0;
list[1]=0;
list[2]=0;
list[3]=1;
list[4]=1;
list[5]=2;
list[6]=1;
list[7]=2;
list[8]=1;
2.1.1实现代码
class CountingSourt extends Sort<num> {
@override
sort() {
//找到最大值
int max = list[0];
for (var i = 1; i < list.length; i++) {
if (list[i]>max) {
max = list[i];
}
}
//开辟内存空间，存储每个整数出现的次数
List<int> counts = List.filled(max+1, 0);
//统计每个整数出现的次数
for (var i = 0; i < list.length; i++) {
counts[list[i]]++;
}
//根据整数出现的次数，对整数进行排序
//按顺序赋值
int index = 0;
for (var i = 0; i < counts.length; i++) {
while(counts[i]-->0){
list[index++] = i;
}
}
}
}
验证一下
main(List<String> args) {
// List<int> list = IntergerTools.random(10000, 1, 20000); //生成10000个数，最小是1，最大是20000
List<int> list = IntergerTools.random(10, 1, 20); //生成10000个数，最小是1，最大是20000
List<Sort> sortList = [
// HeapSort<num>(),//堆排序
// SelectSort<num>(),//选择排序
// BubbleSort2<num>(),//冒泡排序
// BubbleSort1<num>(),//冒泡排序优化1 完全有序，提前终止
// BubbleSort<num>(),//冒泡排序优化2 如果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数
// InsertSort<num>(),//插入排序
// InsertSort1<num>(),//插入排序优化1：改为挪动不是替换
// InsertSort2<num>(),//插入排序优化2：改为二分查找
// MergeSort<num>(),//归并排序
// QuickSort<num>(),//快速排序
// ShellSort<num>(),//希尔排序
CountingSourt(),//计数排序
];
testSorts(list, sortList);
}
void testSorts(List<int> list, List<Sort> sorts) {
print('排序前 ：$list');
for (Sort sort in sorts) {
List<int> newList = List.from(list);
sort.setList(newList);
sort.sortPrint();
Asserts.test(IntergerTools.isAscOrder(sort.list));
print('排序后 ：${sort.list}');
}
sorts.sort(); //比较
for (Sort sort in sorts) {
print(sort);
}
}
结果
排序前 ：[4, 9, 17, 10, 8, 3, 19, 19, 14, 12]
排序后 ：[3, 4, 8, 9, 10, 12, 14, 17, 19, 19]
【CountingSourt】
耗时：0.001s (1ms) 比较：0 交换：0
-----------------
2.1.2 弊端
- 无法对负整数进行排序
- 极其浪费内存空间
- 是个不稳定的排序
- 无法对自定义对象排序
2.1.3 时间复杂度
k代表存储次数的大小，这里是数组的最大值
O(n+k)
2.2 实现2
- 找出数组中最大的数字max和最小的数字min
- 索引0开始以此存放min~max之间数出现的数字
- 每个次数p类加上前面的所有次数num得到的就是元素在有序序列中的位置信息
- num-a 到num-1 就是原生对应的目标数组索引位置
举例
原数组为[7,3,5,8,6,7,4,5]
此时得到的为
| 元素 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 |
| 次数 | 1 | 2 | 4 | 5 | 7 | 8 |
目标数组为
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 元素 | 3 | 4 | 5 | 5 | 6 | 7 | 7 | 8 |
通过观察有以下结论
- 假设list中最小值是min
- list中的元素k对应counts索引是k-min
- list中元素k在有序序列中的索引 counts[k-min]-p,p代表是倒数第几个k
代码思路
- 开辟lists.length长度的空数组
- 遍历lists，得到counts数组
- 倒序遍历lists，按照上述结论得到元素k在有序数组的索引,此时更新counts[k-min]的值减1，代表该位置次数少了1
2.2.1,实现代码
class CountingSourt1 extends Sort<num> {
@override
sort() {
//找到最大值和最小值
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];
}
}
//开辟控件，存储次数
List counts = List.filled(max - min + 1, 0);
//统计每个整数出现的次数
for (var i = 0; i < list.length; i++) {
counts[list[i] - min]++;
}
//累加次数
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--) {
// * 假设list中最小值是min
// * list中的元素k对应counts索引是k-min
// * list中元素k在有序序列中的索引 counts[k-min]-p,p代表是倒数第几个k,通过每次减1，标识该位置次数减少1
int k = list[i];
newList[--counts[k - min]] = list[i];
}
list = newList;
}
}
测试验证
main(List<String> args) {
// List<int> list = IntergerTools.random(10000, 1, 20000); //生成10000个数，最小是1，最大是20000
List<int> list = IntergerTools.random(10, 1, 20); //生成10000个数，最小是1，最大是20000
List<Sort> sortList = [
// HeapSort<num>(),//堆排序
// SelectSort<num>(),//选择排序
// BubbleSort2<num>(),//冒泡排序
// BubbleSort1<num>(),//冒泡排序优化1 完全有序，提前终止
// BubbleSort<num>(),//冒泡排序优化2 如果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数
// InsertSort<num>(),//插入排序
// InsertSort1<num>(),//插入排序优化1：改为挪动不是替换
// InsertSort2<num>(),//插入排序优化2：改为二分查找
// MergeSort<num>(),//归并排序
// QuickSort<num>(),//快速排序
// ShellSort<num>(),//希尔排序
// CountingSourt(),//计数排序
CountingSourt1(),//计数排序 优化
];
testSorts(list, sortList);
}
void testSorts(List<int> list, List<Sort> sorts) {
print('排序前 ：$list');
for (Sort sort in sorts) {
List<int> newList = List.from(list);
sort.setList(newList);
sort.sortPrint();
Asserts.test(IntergerTools.isAscOrder(sort.list));
print('排序后 ：${sort.list}');
}
sorts.sort(); //比较
for (Sort sort in sorts) {
print(sort);
}
}
结果
排序前 ：[2, 12, 13, 14, 18, 16, 15, 15, 3, 16]
排序后 ：[2, 3, 12, 13, 14, 15, 15, 16, 16, 18]
【CountingSourt1】
耗时：0.0s (0ms) 比较：0 交换：0
-----------------
2.2.2 针对思路1改进点
思路1的弊端
- 无法对负整数进行排序
- 极其浪费内存空间
- 是个不稳定的排序
- 无法对自定义对象排序
其中1、2、3在思路2中都得到了改进，但是4依旧没有改进
再次改进
对特定自定义对象排序，要求如下
- 如果自定义对象可以提供用以排序的整数类型，依然可以使用计数排序
例如person类，里面有年龄和姓名，按照年龄进行排序就可以实现计数排序
class Person {
int age;
String name;
Person(this.age,this.name);
@override
String toString() {
// TODO: implement toString
return 'Person 姓名:${this.name} 年龄:${this.age}';
}
}
排序
main(List<String> args) {
List<Person> persons =
[Person(10,'A'),
Person(-1,'B'),
Person(-2,'C'),
Person(2,'D'),
Person(4,'E'),
Person(6,'F'),
Person(12,'G'),
Person(1,'H'),
];
//找到最大值和最小值
int max = persons[0].age;
int min = max;
for (var i = 1; i < persons.length; i++) {
if (persons[i].age > max) {
max = persons[i].age;
}
if (persons[i].age < min) {
min = persons[i].age;
}
}
//开辟空间，存储次数
List counts = List.filled(max - min + 1, 0);
//统计每个整数出现的次数
for (var i = 0; i < persons.length; i++) {
counts[persons[i].age - min]++;
}
//累加次数
for (var i = 1; i < counts.length; i++) {
counts[i] += counts[i-1];
}
//倒序遍历数组，将它放到有序数组的合适位置
//得到元素k在有序数组的索引
List<Person> newList = List(persons.length);
for (var i = persons.length - 1; i >= 0; i--) {
// * 假设list中最小值是min
// * list中的元素k对应counts索引是k-min
// * list中元素k在有序序列中的索引 counts[k-min]-p,p代表是倒数第几个k,通过每次减1，标识该位置次数减少1
int k = persons[i].age;
newList[--counts[k - min]] = persons[i];
}
//将有序数组赋值给list
// persons = newList;
//打印
for (var i = 0; i < newList.length; i++) {
print(newList[i]);
}
}
执行结果
Person 姓名:C 年龄:-2
Person 姓名:B 年龄:-1
Person 姓名:H 年龄:1
Person 姓名:D 年龄:2
Person 姓名:E 年龄:4
Person 姓名:F 年龄:6
Person 姓名:A 年龄:10
Person 姓名:G 年龄:12
可以看到，按照年龄数值排序了
2.2.3 复杂度分析
空间复杂度：
存储次数的counts,假如大小k，以及最后的newList,
所以空间复杂度为O(n+k)
时间复杂度：
统计次数的时间复杂度为O(k),其他几个循环都是O(n)
O(n+k)
网友评论