dart计数排序（Counting Sort）

作者: 锦鲤跃龙 | 来源:发表于2020-11-17 15:28 被阅读0次

[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)

网友评论

本文标题：dart计数排序（Counting Sort）

本文链接：https://www.haomeiwen.com/subject/cxxibktx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！