【算法】计数排序算法的讲授和代码实践

程序员 · 2024-9-27 10:34:47

思绪

计数排序是三个桶排序算法之一（计数排序、基数排序、桶排序），是不须要通过比力就可以对数组举行排序的一种算法。
计数排序的紧张思绪是：
1、新建一个数组，数组长度为原数组中最大的元素 + 1；
2、遍历原数组，将新数组下标即是原数组当前元素的值 + 1，也就是计数了；
3、遍历新数组，按下标依次取出全部元素值不为0的全部下标，而且元素值为几就取反复；
4、全部取出来就是排好序的数组。
另外分析一下计数排序的实用场景：
1、由于是使用数组下标 = 原数组值的情势计数的，全部原数组中的元素只能是大于即是0的数；
2、数组中的元素隔断越小越好。比如如果有一个数组是[1, 2, 99999]，如许的话，固然只有3个元素，却须要创建一个100000巨细的数组才气举行计数排序。
讲授

有数组如下：

我们先创建一个新的数组，长度为原数组中最大值 8 + 1：

然后开始遍历原数组，第一个数为 2，那么新数组下标 2 的值 + 1：

第二个元素为 0，新数组下标 0 的值 + 1：

以此类推，直到遍历完备个原数组，最终新数组如下：

这时间我们就可以遍历新数组，把全部下标取出，次数为下标对应的值。起首取出 0，0 对应的值为 1，取出一个即可：

1 也是同样的，只取出一个：

不停到下标 3 ，下标 3 的值为 2，须要取出两个：

后面的 4 和 7 下标对应的值为 0，不须要取。
直至取完全部元素，数组也就完成了排序：

实现

【算法】计数排序算法的讲授和代码实践

所属分类: 问答交流

新帖推荐: 30日

推荐作品