Quickselect vs Countingselect

Question

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

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

但是，我希望编写一组指南，以确定两种算法中哪一种最适合特定情况。我需要考虑情况，而不是实施哪种算法是更好的选择的指南。

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

Answer 1

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

为什么？好吧，看看计数排序是如何工作的，或者具体来说 - 它如何确定不同元素a和非重复元素b之间的顺序：它使用其整数值来计算此类元素在集合中的位置。看看wikipeida文章中的伪代码。我所指的可以在这一行中看到：

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

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

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

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