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

Question

快速排序：

• 最坏情况o(n^2)
• 平均病例O(nlogn)

计数排序：

• 在所有情况下o(n)

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

如果存在这两个条件，为什么快速排序比计数排序还要好呢？

Answer 1

不同类型的人之间并不总是“更好”。在某些情况下，可能出于以下几个原因而倾向于快速排序：

1. 快速排序已经到位，与计数排序不同，排序必须创建多个数组(例如，使用更多内存)才能完成其工作。
2. 看起来好像计数排序是O(n)，但是看看必须创建的中间计数数组。计数数组长度实质上是原始数组中最大元素和最小元素之间的差异。如果范围真的很大，这个计数阵列是巨大的。例如，如果数组只有两个元素，但这两个元素是1和9999999，怎么办？这个计数数组必须被处理(所有这些求和和计数的东西)。实际上，计数排序的运行时间是O(n+k)，其中k是原始数组中最大元素和最小元素之间的差异。
3. 最后，如果要排序的元素不是数字，则计算排序seems...difficult来实现。它对字符串是如何工作的？