拜托，面试别再问我计数和桶排序了！！！

柔光的暖阳◎ 2023-07-13 03:22 60阅读 0赞

时间复杂度为O(n)的排序，除了**基数排序**(Radix Sort)，还有**计数排序**(Counting Sort)。今天，1分钟，通过几幅图，争取让大家搞懂计数排序。

**计数排序的适用范围？**

待排序的元素在某一个范围\[MIN, MAX\]之间。

*画外音：很多业务场景是符合这一场景，例如uint32的数字排序位于\[0, 2^32\]之间。*

**计数排序的空间复杂度？**

计数排序需要一个辅助空间，空间大小为O(MAX-MIN)，用来存储所有元素出现次数（“计数”）。

*画外音：计数排序的核心是，空间换时间。*

**计数排序的关键步骤？**

**步骤一**：扫描待排序数据arr\[N\]，使用计数数组counting\[MAX-MIN\]，对每一个arr\[N\]中出现的元素进行计数；

**步骤二**：扫描计数数组counting\[\]，还原arr\[N\]，排序结束；

举个**栗子**：

假设待排序的数组，

arr=\{5, 3, 7, 1, 8, 2, 9, 4, 7, 2, 6, 6, 2, 6, 6\}

很容易发现，待排序的元素在\[0, 10\]之间，可以用counting\[0,10\]来存储计数。

**第一步：统计计数**

![format_png][]

扫描未排序的数组arr\[N\]，对每一个出现的元素进行计数。

扫描完毕后，计数数组counting\[0, 10\]会变成上图中的样子，如粉色示意，**6**这个元素在arr\[N\]中出现了**4**次，在counting\[0, 10\]中，**下标为6**的位置**计数是4**。

**第二步：还原数组**

![format_png 1][]

扫描计数数组counting\[0, 10\]，通过每个元素的计数，还原arr\[N\]。

如上图粉色示意，count\[0, 10\]**下标为6**的位置**计数是4**，排完序是**4个连续的6**。

从counting下标MIN到MAX，逐个还原，填满arr\[N\]时，排序结束。

**神奇不神奇！！！**

**计数排序**(Counting Sort)，总结：

*  计数排序，时间复杂度为O(n)；
 *  当待排序元素个数很多，但值域范围很窄时，计数排序是很节省空间的

\----------------------------------------------------------------------------------------------------------------------------------

排序，面试中考察基本功问的比较多的问题。

时间复杂度为O(n)的排序，常见的有三种：

*  **基数排序**(Radix Sort)
 *  **计数排序**(Counting Sort)
 *  **桶排序**(Bucket Sort)

今天，1分钟，争取让大家搞懂桶排序。

*画外音：百度“桶排序”，很多文章是错误的，本文内容与《算法导论》中的桶排序保持一致。*

桶排序的适用范围是，待排序的元素能够均匀分布在某一个范围\[MIN, MAX\]之间。

*画外音：很多业务场景是符合这一场景，待排序的元素在某一范围内，且是均匀分布的。*

桶排序需要两个辅助空间：

*  第一个辅助空间，是**桶空间**B
 *  第二个辅助空间，是**桶内的元素链表空间**

总的来说，空间复杂度是O(n)。

桶排序有两个关键步骤：

*  扫描待排序数据A\[N\]，对于元素A\[i\]，放入对应的桶X
 *  A\[i\]放入桶X，如果桶X已经有了若干元素，使用插入排序，将arr\[i\]放到桶内合适的位置

*画外音：*

*（1）桶X内的所有元素，是一直有序的；*

*（2）插入排序是稳定的，因此桶内元素顺序也是稳定的；*

当arr\[N\]中的所有元素，都按照上述步骤放入对应的桶后，就完成了全量的排序。

桶排序的伪代码是：

bucket\_sort(A\[N\])\{

for i =1 to n\{

将A\[i\]放入对应的桶B\[X\];

使用插入排序，将A\[i\]插入到B\[X\]中正确的位置;

将B\[X\]中的所有元素，按顺序合并，排序完毕;

举个**栗子**：

假设待排序的数组均匀分布在\[0, 99\]之间：

\{5,18,27,33,42,66,90,8,81,47,13,67,9,36,62,22\}

可以设定10个桶，申请额外的空间bucket\[10\]来作为辅助空间。其中，每个桶bucket\[i\]来存放\[10\*i, 10\*i+9\]的元素链表。

![format_png 2][]

上图所示：

*  待排序的数组为unsorted\[16\]
 *  桶空间是buket\[10\]
 *  扫描所有元素之后，元素被放到了自己对应的桶里
 *  每个桶内，使用插入排序，保证一直是有序的

例如，标红的元素66, 67, 62最终会在一个桶里，并且使用插入排序桶内保持有序。

最终，每个**桶**按照次序输出，排序完毕。

**神奇不神奇！！！**

桶排序(Bucket Sort)，总结：

*  桶排序，是一种复杂度为O(n)的排序
 *  桶排序，是一种稳定的排序
 *  桶排序，适用于数据均匀分布在一个区间内的场景

希望这一分钟，大家有收获。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9ZcmV6eGNraFlPeTRXbHlRM0pRcHZja0U2akhmNTNmdTdJbVY3RFJ1Z1RKMWR0RWN6ZDdpY0NPSk43RVdmbktWTWljTlFGZEtPcWRnU3JaNnBvZHhmU3VRLzY0MA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9ZcmV6eGNraFlPeTRXbHlRM0pRcHZja0U2akhmNTNmdWliQUJXRFI1WEVZeVAzMjNubzA3akJkVjFWVlN5TkJzVGVrVWYzd1NyclJ3eDNsYkNpYzJXazd3LzY0MA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9ZcmV6eGNraFlPeERhcDlpY3RiTkE4eENZb25zUzNLOGhTVTFSVEpXYjM3OHJpY0hrdG1nbmliSU9JRnZPaWJPV0ZTMEowU2ZwemJQYXVBVWJiUTVIekFJWkEvNjQw?x-oss-process=image/format,png