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

归并排序

第一，归并排序可以是稳定的排序算法。
第二，归并排序的时间复杂度是 O(nlogn)
第三，归并排序的空间复杂度任何情况下都是 O(nlogn)，它有一个致命的“弱点”，那就是归并排序不是原地排序算法。最大空间复杂度是 O(n)。

快速排序

快速排序不是原地排序算法
快速排序并不是一个稳定的排序算法。
快排的时间复杂度在大部分情况下的时间复杂度都可以做到 O(nlogn)，只有在极端情况下，才会退化到 O(n2)。

内容小结

归并排序和快速排序是两种稍微复杂的排序算法，它们用的都是分治的思想，代码都通过递归来实现，过程非常相似。理解归并排序的重点是理解递推公式和 merge() 合并函数。同理，理解快排的重点也是理解递推公式，还有 partition() 分区函数。

归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法，这也使它存在致命的缺点，即归并排序不是原地排序算法，空间复杂度比较高，是 O(n)。正因为此，它也没有快排应用广泛。

快速排序算法虽然最坏情况下的时间复杂度是 O(n2)，但是平均情况下时间复杂度都是 O(nlogn)。不仅如此，快速排序算法时间复杂度退化到 O(n2) 的概率非常小，我们可以通过合理地选择 pivot 来避免这种情况。