algorithm - 快速选择与计数选择

Question

基于快速排序的快速选择和基于计数排序的计数选择。

每个都能够找到未排序/排序列表/数组中的第 k 个最小元素。

但是，我希望编写一套指南来决定这两种算法中的哪一种最适合特定情况。我需要考虑情况，而不是实施关于哪种算法是更好选择的指导方针。

为此，我需要一些帮助来区分哪种算法在某些领域具有特定优势等。

Answer 1

(1)计数排序要求元素是可枚举的（元素到整数之间存在唯一的映射）才能正常工作。另一方面，快速排序只需要在每两个元素之间定义良好的比较操作（比较函数应该是可传递的- 或者直观地 - 不是自相矛盾的）。
这是您应该面对的一个主要问题 - 不能总是使用计数选择，而可以使用快速选择。

为什么？好吧，看看计数排序是如何工作的，或者具体来说——它如何确定不同元素a和不同元素之间的排序b：它使用它的整数值来计算这种元素在集合中的位置。看看维基百科文章中的伪代码。我所指的可以在以下几行中看到：

for each input item x:
    Count[key(x)] = Count[key(x)] + 1

值，是元素的key(x)枚举——如果它不存在，会key(x)产生什么？该算法将如何工作？
出于同样的原因，这也适用于计数选择算法，它也使用key(element)来计算该元素在集合中重复的次数。

(2)如果元素的范围很大，则另一个问题是效率——计数效率低下，因为它在元素范围内是线性的。
QuickSelect，基于快速排序的运行时间平均是线性的，但有时可能会衰减到二次时间复杂度。

(3)另一个问题是空间——计数选择需要额外的空间，在元素的范围内是线性的，而快速选择不需要。