跳转至

快速排序

算法

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

快速排序分为三个过程:

  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/


评论