12|排序(下):如何用快排思想在O(n)内查找第K大元素?

[hfuuss]

归并排序和快速排序。这两种排序算法适合大规模的数据排序，比上一节讲的那三种排序算法要更常用。

[hfuuss]

快排核心思想就是分治和分区，我们可以利用分区的思想，来解答开篇的问题:O(n)时间复杂度内求无序数组中的第K大元素。比如，4， 2， 5， 12， 3这样一组 数据，第3大元素就是4。 我们选择数组区间A[0...n-1]的最后一个元素A[n-1]作为pivot，对数组A[0...n-1]原地分区，这样数组就分成了三部分，A[0...p-1]、A[p]、A[p+1...n-1]。 如果p+1=K，那A[p]就是要求解的元素;如果K>p+1, 说明第K大元素出现在A[p+1...n-1]区间，我们再按照上面的思路递归地在A[p+1...n-1]这个区间内查找。同 理，如果K<p+1，那我们就在A[0...p-1]区间查找。

[hfuuss]

归并排序和快速排序是两种稍微复杂的排序算法，它们用的都是分治的思想，代码都通过递归来实现，过程非常相似。理解归并排序的重点是理解递推公式 归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法，这也使它存在致命的缺点，即归并排序不是原地排序算法，空间复杂度比较高，是O(n)。 正因为此，它也没有快排应用广泛。