Quickselect vs Countingselect

Question

快速选择，基于快速排序，计数选择，基于计数排序。

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

但是，我希望编写一组指导原则，以确定这两种算法中的哪一种最适合特定情况。我需要考虑情况，然后执行指导方针，以确定哪种算法是更好的选择。

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

Answer 1

(1) Count sort要求元素为 (存在元素到整数的唯一映射)才能正常工作。另一方面，快速排序只需要定义好的每两个元素之间的比较操作(比较函数应该是transitive的--或者直观地说--不是自相矛盾的)。

这是你应该面对的一个主要问题-计数选择不能总是使用，而快速选择可以。

为什么？那么，让我们来看看count sort是如何工作的，或者更具体地说，它是如何确定distinct元素a和distinct元素b之间的顺序的:它使用它的整数值来计算这种类型的元素在集合中的位置。看一看pseudo-code in the wikipeida article。我所指的内容可以在下面这几行中看到：

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

key(x)值是元素的枚举-如果它不存在，key(x)将产生什么？算法将如何工作？

出于同样的原因，这也适用于计数选择算法，它还使用key(element)来计算此元素在集合中重复的次数。

(2)如果元素的范围很大，那么还有一个问题是效率-其中计数效率很低，因为它在元素范围内是线性的。

基于快速排序的QuickSelect平均运行时间是线性的，但有时可能会衰减到二次时间复杂度。

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