基于计数排序，基于快速排序和计数选择进行快速选择 .
每个都能够在未排序/排序的列表/数组中找到第k个最小元素 .
但是，我希望编写一套指南来决定哪种算法最适合特定情况 . 我需要考虑情况，而不是实现哪种算法是更好的选择 .
为此，我需要帮助区分哪种算法在某些领域具有特定的优势等 .
(1) 计数排序要求元素为enumerable（元素到整数的唯一映射）才能正常工作 . 另一方面，快速排序只需要在每两个元素之间定义一个比较操作（比较函数应该是transitive - 或直观地 - 不自相矛盾） .这是你应该面对的一个主要问题 - the counting selection cannot always be used, while quick selection can.
为什么？那么，看看count sort如何工作，或者具体 - 它如何确定不同元素 a 和不同元素 b 之间的顺序：它使用其整数值来计算这种元素在集合中的方式 . 看看pseudo-code in the wikipeida article . 我所指的内容可以从以下几行看出：
a
b
for each input item x: Count[key(x)] = Count[key(x)] + 1
key(x) 值是元素的枚举 - 如果它不存在， key(x) 会产生什么？算法将如何运作？这也适用于计数选择算法，出于同样的原因，它还使用 key(element) 来计算此元素在集合中重复的次数 .
key(x)
key(element)
(2) 如果 range of elements 很大，则另一个问题是效率 - 计数效率低，因为它在元素范围内是线性的 .基于快速排序运行时间的QuickSelect平均线性，但有时可能衰减到二次时间复杂度 .
(3) 另一个问题是 space - 计数选择需要额外的空间，在元素范围内是线性的，而快速选择则不需要 .
1 回答
(1) 计数排序要求元素为enumerable（元素到整数的唯一映射）才能正常工作 . 另一方面，快速排序只需要在每两个元素之间定义一个比较操作（比较函数应该是transitive - 或直观地 - 不自相矛盾） .
这是你应该面对的一个主要问题 - the counting selection cannot always be used, while quick selection can.
为什么？那么，看看count sort如何工作，或者具体 - 它如何确定不同元素
a和不同元素b之间的顺序：它使用其整数值来计算这种元素在集合中的方式 . 看看pseudo-code in the wikipeida article . 我所指的内容可以从以下几行看出：key(x)值是元素的枚举 - 如果它不存在，key(x)会产生什么？算法将如何运作？这也适用于计数选择算法，出于同样的原因，它还使用
key(element)来计算此元素在集合中重复的次数 .(2) 如果 range of elements 很大，则另一个问题是效率 - 计数效率低，因为它在元素范围内是线性的 .
基于快速排序运行时间的QuickSelect平均线性，但有时可能衰减到二次时间复杂度 .
(3) 另一个问题是 space - 计数选择需要额外的空间，在元素范围内是线性的，而快速选择则不需要 .