

快速排序

算法

快速排序是 分治 地来将一个数组排序。

快速排序分为三个过程：

1. 将数列划分为两部分（不是直接分，要求保证相对大小关系）
2. 递归到两个子序列中分别进行快速排序
3. 不用合并，因为此时数列已经完全有序

和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。

第三步中的序列已经分别有序且第一个序列中的数都小于第二个数，所以直接拼接起来就好了。

具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。

怎么操作呢？为了保证平均时间复杂度，一般是随机选择一个数 m 来当做两个子数列的分界。

之后，维护一前一后两个指针 p 和 q，依次考虑当前的数是否放在了应该放的位置（前还是后），当前位置放对了之后，再移动指针继续处理，直到两个指针相遇。

如果当前的数没放对呢？比如说如果后面的指针 q 遇到了一个比 m 小的数，那么可以交换 p 和 q 位置上的数，再把 p 向后移一位。

其实，快速排序没有指定应如何具体实现第一步，不论是选择 m 的过程还是划分的过程，都不是只有一种实现方法。

一般我们说的快速排序的时间复杂度是平均为 $O(n\log n)$ ，最坏是 $O(n^2)$ ，实践中几乎不可能达到最坏情况。且因为快速排序的内存访问遵循局部性原理，多数情况下快速排序的表现大幅优于堆排序等其他复杂度为 $O(n \log n)$ 的排序算法。

其实，在选择 m 的过程中使用 Median of Medians 算法，就可以保证最坏时间复杂度为 $O(n\log n)$ ，但是由于其过于复杂，实践中一般不使用。

线性找第 k 大的数

找第 k 大的数（K-th order statistic），最简单的方法是先排序，然后直接找到第 k 大的位置的元素。这样做的时间复杂度是 $O(n\log n)​$ ，对于这个问题来说很不划算。事实上，我们有时间复杂度 $O(n)​$ 的解法。

考虑快速排序的划分过程，在快速排序的“划分”结束后，数列 $A_{p} \cdots A_{r}​$ 被分成了 $A_{p} \cdots A_{q}​$ 和 $A_{q+1} \cdots A_{r}​$ ，此时可以按照左边元素的个数（ $q - p + 1​$ ）和 k 的大小关系来判断是只在左边还是只在右边递归地求解。

可以证明，在期望意义下，程序的时间复杂度为 $O(n)$ 。

参考

https://stackoverflow.com/questions/22339240/what-algorithms-are-used-in-c11-stdsort-in-different-stl-implementations

https://en.cppreference.com/w/cpp/algorithm/sort

http://irootlee.com/juicer_locality/

---

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论