为什么快速排序比计数排序更好？

Question

快速排序：

• 最坏时间复杂度O(n^2)
• 平均时间复杂度O(nlogn)

计数排序：

• 在所有情况下时间复杂度都是O(n)

快排和计数排序都是稳定的算法。

如果这两个条件都满足，为什么快速排序仍然比计数排序更好呢？

- antara_mishra

---

你有检查计数排序的限制条件吗？我的意思是，你可以运行计数排序的前提条件是什么？ - taskinoor

快速排序通常不被认为是一种稳定的排序算法。计数排序在可以排序的类型上有重要约束。 - Jonathan Leffler

“stable”在排序中有特定的意义，即如果两个待比较的条目相等，则它们在排序结果中的相对顺序与排序开始前它们的顺序相同。快速排序是非常可靠的；但它不是稳定的。（参见我之前评论中的维基百科链接-它指出了快速排序不是稳定的。它还提供了关于何为稳定排序的信息的链接。） - Jonathan Leffler

这个问题被过分苛刻地评判了。这是一个合理的问题，有一个合理的答案。对于“better”是一种观点的任何抱怨都可以通过编辑来解决。 - Eric Postpischil

计数排序在缓存方面并不友好。一个体面的通用计数排序通常需要一个以MB为单位的计数数组。CPU缓存可能无法容纳那么多数据，而且由于在计数数组中命中任何索引的机会相当随机，你将不断遇到缓存未命中的情况。 - Yashas

Answer 1

并非所有的排序算法都比其他算法更好。在某些情况下，由于以下几个原因，快速排序可能会被优先选择：

1. 与计数排序不同，快速排序是原地排序的，不需要创建多个数组（例如使用更多内存）来完成工作。

2. 看起来计数排序是O(n)的，但请看一下必须创建的中间计数数组。计数数组的长度实际上是原始数组中最大元素和最小元素之间的差异。如果范围非常大，那么这个计数数组就会非常庞大。例如，如果您的数组只有两个元素，但这两个元素是1和9999999？而且这个计数数组必须被处理（所有那个求和和计数的东西）。因此，计数排序的运行时间实际上是O(n+k)，其中k是原始数组中最大元素和最小元素之间的差异。

3. 最后，如果要排序的元素不是数字，计数排序似乎很难实现。对于字符串，它会怎么工作呢？

- Phil

---

简言之，计数排序无法处理一般的任意长度字符串。 - Jonathan Leffler

感谢您，第二点很令人满意，非常感谢。 - antara_mishra

k 可以被视为不同元素的数量，而不是元素的范围，但是不同元素的数量远小于范围的情况很少见（例如具有值为1和9999999的两个不同元素的示例），需要进行映射以将元素值转换为映射索引。 - rcgldr