Swift经典排序算法-计数排序法

一、小序

我们先讲解一道算法题目：数组中有10个随机数值，数值取值范围为从0到5，我们如何用最快的速度把这10个整数从小到大进行排序。

首先你会想到我们之前学的快速排序这个算法，因为快速排序算法的时间复杂度只为O(nlogn)。其实这种方法还是不够快，那有没有比快速排序算法更快的排序方法呢？你心中不免疑虑 ？？？”时间复杂度为O(nlogn)的快速排序？？不是最快的？？？“

让我们先来回顾一下经典的排序算法，无论是归并排序，冒泡排序还是快速排序等等，都是基于元素之间的比较来进行排序的。但是有一种特殊的排序算法叫计数排序，这种排序算法不是基于元素比较，而是利用数组下标来确定元素的正确位置。

在刚才的题目里，随机整数的取值范围是从0到5，那么这些整数的值肯定是在0到10这11个数里面。于是我们可以建立一个长度为6的数组，数组下标从0到5，元素初始值全为0，如下所示：

先假设10个随机整数的值是：【3,5,1,3,2,5,4,1,3,2】

让我们对这个无序的随机数组进行遍历，每一个整数按照其值对号入座，对应数组下标的元素进行加1操作。

例如：第一个整数是3，那么数组下标为3的元素加1：

第二个整数是5，那么数组下标为5的元素加1：

继续遍历数列并修改数组…

最终，数列遍历完毕时，数组的状态如下：

数组中的每一个值，代表了数列中对应整数的出现次数。

有了这个统计结果，排序就很简单了，直接遍历数组，输出数组元素大于0的下标值，元素的值是几，就输出几次：

【1、1、2、2、3、3、3、4、5、5】

显然，这个输出的数列已经是有序的了。

以上就是计数排序的基本过程，它适用于一定范围的整数排序。在取值范围不是很大的情况下，它的性能在某些情况甚至快过那些O(nlogn)的排序，例如快速排序、归并排序。

二、动画演示【其实上面例子更加明了】

三、代码实现

更多算法知识，关注微信公众号：⬇️