找到数组中的第n个最小元素而不进行排序？

Question

我想写一个程序来找到第n个最小的元素,而不使用任何排序技术.

我们可以递归地进行,分割和征服风格,如快速排序？

如果没有,怎么样？

Answer 1

您可以在此处找到有关该问题的信息:选择算法.

Answer 2

您所指的是选择算法,如前所述.具体来说,您对quicksort的引用表明您正在考虑基于分区的选择.

以下是它的工作原理:

• 就像在Quicksort中一样,你首先要选择一个好的支点:你认为这几乎是你列表中的一半.然后,您将浏览整个项目列表,这些项目来回交换,直到所有项目都不在您的数据库的开头,并且所有大于您的项目的项目都在最后.你的支点进入中间的剩余点.
• 通常在快速排序中你会在枢轴的两侧递归,但是对于选择算法,你只会在包含你感兴趣的索引的那一侧递归.所以,如果你想找到第三个最低值,那么,递归在哪一方包含索引2(因为索引0是第一个最低值).
• 当您将区域缩小到一个索引时,可以停止递归.最后,您将拥有一个"m-1"最小对象的未排序列表,以及另一个"nm"最大对象的未排序列表.第m个对象将在其间.

此算法也适用于查找最高m个元素的排序列表...只需选择第m个最大元素,然后对其上方的列表进行排序.或者,对于速度稍快的算法,请执行Quicksort算法,但拒绝递归到与要查找已排序值的区域不重叠的区域.

关于这一点的真正好处是它通常在O(n)时间内运行.第一次,它看到整个列表.在第一次递归时,它看到大约一半,然后是四分之一等等.因此,它查看大约2n个元素,因此它在O(n)时间内运行.不幸的是,就像在快速排序中一样,如果你一直选择一个不好的支点,你将在O(n ²)时间内运行.