下载掌阅APP，畅读海量书库
立即打开
我们在生活中到处都会用到排序，例如比赛、奖学金评选、推荐系统等。排序算法有很多种，能不能找到更快速、高效的排序算法呢？
有人曾通过实验，对各种排序算法效率做了对比（单位：毫秒），对比结果如下表所示。
从上表可以看出，如果对10万个数据进行排序，则冒泡排序需要8174毫秒，快速排序只需3.634毫秒！
快速排序是比较快速的排序方法，由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据小，然后按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
合并排序每次都从中间位置把问题一分为二，一直分解到不能再分时再执行合并操作。合并排序的划分很简单，但合并操作需要在辅助数组中完成，是一种异地排序的方法。合并排序分解容易、合并难，属于“先易后难”。而快速排序是原地排序，不需要辅助数组，但分解困难、合并容易，属于“先苦后甜”。
快速排序是基于分治策略的，其算法思想如下。
（1）分解：先从数列中取出一个元素作为基准元素。以基准元素为标准，将问题分解为两个子序列，使小于或等于基准元素的子序列在左侧，使大于基准元素的子序列在右侧。
（2）治理：对两个子序列进行快速排序。
（3）合并：将排好序的两个子序列合并在一起，得到原问题的解。
如何分解是一个难题，因为如果基准元素选取不当，就有可能分解成规模为0和 n -1的两个子序列，这样快速排序就退化为冒泡排序了。
例如对于序列(30,24,5,58,18,36,12,42,39)，第1次选取5作为基准元素，分解后如下图所示。
第2次选取12作为基准元素，分解后如下图所示。
这样做的效率是最低的，最理想的状态是把序列分解为两个规模相当的子序列，那么怎样选取基准元素呢？一般来说，对基准元素的选取有以下几种方法：
● 取第一个元素；
● 取最后一个元素；
● 取中间位置的元素；
● 取第一个元素、最后一个元素、中间位置的元素三者的中位数；
● 取第一个元素和最后一个元素之间位置的随机数 k （low≤ k ≤high），选R[ k ]作为基准元素。
因为并没有明确说明哪一种基准元素选取方案最好，所以在此选取第一个元素作为基准，以说明快速排序的执行过程。
假设当前待排序的序列为r[low: high]，其中low≤high。
（1）取数组的第一个元素作为基准元素pivot=r[low]， i =low， j =high。
（2）从右向左扫描，找小于或等于pivot的数，如果找到，则r[ i ]和r[ j ]交换， i ++。
（3）从左向右扫描，找大于pivot的数，如果找到，则r[ i ]和r[ j ]交换， j --。
（4）重复第2～3步，直到 i 和 j 重合，返回mid= i ，该位置的数正好是pivot元素。
至此完成一趟排序。此时以mid为界，将原数据分为两个子序列，左侧子序列都比pivot小，右侧子序列都比pivot大。然后分别对这两个子序列进行快速排序。
这里以序列(30,24,5,58,18,36,12,42,39)为例，演示快速排序过程。
（1）初始化。 i =low， j =high，pivot=r[low]=30。
（2）向左走。从数组的右边位置向左找，一直找小于或等于pivot的数，找到r[ j ]=12。
r[ i ]和r[ j ]交换， i ++，如下图所示。
（3）向右走。从数组的左边位置向右找，一直找比pivot大的数，找到r[ i ]=58。
r[ i ]和r[ j ]交换， j --，如下图所示。
（4）向左走。从数组的右边位置向左找，一直找小于或等于pivot的数，找到r[ j ]=18。
r[ i ]和r[ j ]交换， i ++，如下图所示。
（5）向右走。从数组的左边位置向右找，一直找比pivot大的数，此时 i = j ，第一趟排序结束，返回 i 的位置，mid= i ，如下图所示。
此时以mid为界，将原序列分为两个子序列，左侧子序列都比pivot小，右侧子序列都比pivot大。然后分别对两个子序列(12,24,5,18)、(36,58,42,39)进行快速排序。
（1）划分函数。划分函数对原序列进行分解，将其分解为两个子序列，以基准元素pivot为界，左侧子序列都比pivot小，右侧子序列都比pivot大。先从右向左扫描，找小于或等于pivot的数，找到后两者交换（在r[ i ]和r[ j ]交换后， i ++）；再从左向右扫描，找比基准元素大的数，找到后两者交换（在r[ i ]和r[ j ]交换后， j --）。扫描交替进行，直到 i = j 时停止，返回划分的中间位置 i 。
（2）快速排序。首先对原序列划分，得到划分的中间位置mid；然后以中间位置为界，分别对左半部分(low,mid-1)执行快速排序，对右半部分(mid+1,high)执行快速排序。递归结束的条件是low≥high。
这里将快速排序分为最好情况、最坏情况和平均情况进行算法分析。
分解：划分Partition时需要扫描每个元素，每次扫描的元素个数都不超过 n ，因此时间复杂度为 O ( n )。
解决子问题：在最理想情况下，每次划分都将问题分解为两个规模为 n /2的子问题，递归求解两个规模为 n /2的子问题，所需时间为2 T ( n /2)，如下图所示。
合并：因为是原地排序，所以合并操作不需要时间复杂度，如下图所示。
所以总运行时间如下：
当 n >1时，可以递推求解：
递推最终的规模为1，令 n =2 x ，则 x =log n ，那么
快速排序算法在最好情况下的时间复杂度为 O ( n log n )。
空间复杂度：程序中的变量的辅助空间是常数阶的，递归调用所使用的栈空间为递归树的高度 O (log n )，快速排序算法在最好情况下的空间复杂度为 O (log n )。
分解：划分函数Partition时需要扫描每个元素，每次扫描的元素个数都不超过 n ，因此时间复杂度为 O ( n )。
解决子问题：在最坏情况下，每次划分并将问题分解后，基准元素的左侧（或者右侧）都没有元素，基准元素的另一侧为1个规模为 n -1的子问题，递归求解这个规模为 n -1的子问题，所需时间为 T ( n -1)，如下图所示。
合并：因为是原地排序，所以合并操作不需要时间复杂度，如下图所示。
所以总运行时间如下：
当 n >1时，可以递推求解：
快速排序算法在最坏情况下的时间复杂度为 O ( n 2 )。
空间复杂度：程序中的变量的辅助空间是常数阶的，递归调用所使用的栈空间为递归树的高度 O ( n )，快速排序算法在最坏情况下的空间复杂度为 O ( n )。
假设划分后基准元素的位置在第 k （ k =1,2,…, n ）个，如下图所示。
则：
由归纳法可以得出， T ( n )的数量级也为 O ( n log n )。快速排序算法在平均情况下的时间复杂度为 O ( n log n )。递归调用所使用的栈空间为 O (log n )，快速排序算法在平均情况下的空间复杂度为 O (log n )。
从上述算法可以看出，每次交换都是和基准元素进行交换，实际上没必要这样做。我们的目的是把原序列分成以基准元素为界的两个子序列，左侧子序列小于或等于基准元素，右侧子序列大于基准元素。那么有很多方法可以实现：可以从右向左扫描，找小于或等于pivot的数r[ j ]，然后从左向右扫描，找大于pivot的数r[ i ]，将r[ i ]和r[ j ]交换，一直交替进行，直到 i 和 j 相遇为止，这时将基准元素与r[ i ]交换即可。这样就完成了一次划分过程，但交换元素的次数少了很多。
假设当前待排序的序列为r[low: high]，其中low≤high。
（1）首先取数组的第一个元素作为基准元素，pivot=r[low]， i =low， j =high。
（2）从右向左扫描，找小于或等于pivot的数r[ i ]。
（3）从左向右扫描，找大于pivot的数r[ j ]。
（4）r[ i ]和r[ j ]交换， i ++， j --。
（5）重复第2～4步，直到 i 和 j 相等。此时如果r[ i ]大于pivot，则r[ i -1]和基准元素r[low]交换，返回该位置，mid= i -1；否则r[ i ]和r[low]交换，返回该位置，mid= i 。该位置的数正好是基准元素。
至此完成一趟排序。此时以mid为界，将原数据分为两个子序列，左侧子序列都比pivot小，右侧子序列都比pivot大。然后分别对这两个子序列进行快速排序。
这里以序列(30,24,5,58,18,36,12,42,39)为例，演示快速排序的优化过程。
（1）初始化。 i =low， j =high，pivot=r[low]=30。
（2）向左走。从数组的右边位置向左找，一直找小于或等于pivot的数，找到r[ j ]=12。
（3）向右走。从数组的左边位置向右找，一直找比pivot大的数，找到R[ i ]=58。
r[ i ]和r[ j ]交换， i ++， j --。
（4）向左走。从数组的右边位置向左找，一直找小于或等于pivot的数，找到r[ j ]=18。
（5）向右走。从数组的左边位置向右找，一直找比pivot大的数，这时 i = j ，停止。
（6）r[ i ]小于pivot，r[ i ]和r[low]交换，返回 i 的位置，mid= i ，第一趟排序结束。
此时以mid为界，将原数据分为两个子序列，左侧子序列都比pivot小，右侧子序列都比pivot大，如下图所示。然后分别对两个子序列(18,24,5,12)、(36,58,42,39)进行快速排序。
算法代码：
