快速排序

韩冰

<>分而治之方法还可以用于实现另一种完全不同的排序方法，这种排序法称为快速排序（quick sort）。在这种方法中， n 个元素被分成三段（组）：左段l e f t，右段r i g h t和中段m i d d l e。中段仅包含一个元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。因此l e f t和r i g h t中的元素可以独立排序，并且不必对l e f t和r i g h t的排序结果进行合并。m i d d l e中的元素被称为支点( p i v o t )。图1 4 - 9中给出了快速排序的伪代码。


/ /使用快速排序方法对a[ 0 :n- 1 ]排序

2 L" }; }! b# `0 v. S& J从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e，该元素为支点

2 Q; h. M2 W1 i# b( o( P7 p把余下的元素分割为两段left 和r i g h t，使得l e f t中的元素都小于等于支点，而right 中的元素都大于等于支点
2 j4 |! S( O. O& R+ t! d
7 J0 S+ U# W; N( k  R& r6 Q递归地使用快速排序方法对left 进行排序

, e( f2 I/ W: k( H2 y  O递归地使用快速排序方法对right 进行排序

所得结果为l e f t + m i d d l e + r i g h t

图14-9 快速排序的伪代码


考察元素序列[ 4 , 8 , 3 , 7 , 1 , 5 , 6 , 2 ]。假设选择元素6作为支点，则6位于m i d d l e；4，3，1，5，2位于l e f t；8，7位于r i g h t。当left 排好序后，所得结果为1，2，3，4，5；当r i g h t排好序后，所得结果为7，8。把right 中的元素放在支点元素之后， l e f t中的元素放在支点元素之前，即可得到最终的结果[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。
) e& K9 d5 j0 f5 I, Y( K) z
把元素序列划分为l e f t、m i d d l e和r i g h t可以就地进行（见程序1 4 - 6）。在程序1 4 - 6中，支点总是取位置1中的元素。也可以采用其他选择方式来提高排序性能，本章稍后部分将给出这样一种选择。
2 @% }# l6 }- Y# c& r
程序14-6 快速排序
. a$ }' T% X0 \4 c$ i2 Q+ A$ e9 e9 f
4 v# }4 L4 i7 t; Ntemplate<CLASS T>
) m* ~* K7 Q& o; d9 X: ?5 e
( }# m; l$ D- x+ ]void QuickSort(T*a, int n)

{// 对a[0:n-1] 进行快速排序

( j6 ^8 J9 R  I( U: I& P- L7 e{// 要求a[n] 必需有最大关键值
) l9 e- @6 y4 ^3 O+ x8 q/ k
quickSort(a, 0, n-1);
7 a/ j- t$ _- t0 F* O0 H2 Y" I
6 p1 Y) g. G" \template<CLASS T>

void quickSort(T a[], int l, int r)
( b( ]: y# q; o" P9 ~( c4 n$ D( P
{// 排序a [ l : r ]， a[r+1] 有大值
4 p3 G, f5 g$ o2 A0 M0 M# J
if (l &gt;= r) return;

int i = l, // 从左至右的游标
  Z( _7 K: C. ~# ~
, u- R1 @* l0 {: r! J, F& ]j = r + 1; // 从右到左的游标
7 W7 p! W$ w$ w- w! `/ N
T pivot = a[l];

// 把左侧&gt;= pivot的元素与右侧&lt;= pivot 的元素进行交换
' ~8 [5 V2 \8 N/ |* u) M  k4 B
2 R  e$ s" z  R  F( I; M1 awhile (true) {
; W! Q. J% W3 X6 Q/ ~8 ]" b/ I
do {// 在左侧寻找&gt;= pivot 的元素
2 c) _% z2 P. b4 F8 B5 r. E
! j" p. }5 _9 A8 q# c. _/ m( Ei = i + 1;

2 `" k) y- N3 C6 @2 k3 u0 k} while (a &lt; pivot);

do {// 在右侧寻找&lt;= pivot 的元素
. ]0 Y3 B3 p1 @! D% ?/ {
! Z3 }2 w" ^8 [j = j - 1;

: P) U# n6 Y' ~3 `+ l5 f$ P0 S} while (a[j] &gt; pivot);
5 I2 L; G- {* Q3 i; \2 K
9 b8 x8 G5 k7 qif (i &gt;= j) break; // 未发现交换对象
4 g1 Q" s9 a- ~* p0 ]
Swap(a, a[j]);

}
9 p: K- n5 A* c8 c  M
" c3 o2 O) c5 H: }// 设置p i v o t

% Z0 L0 T1 A( ~a[l] = a[j];

7 }; A( `4 y* la[j] = pivot;
) h5 v6 B& p8 K5 p% D
quickSort(a, l, j-1); // 对左段排序
1 _' |6 N9 `% \. {9 S8 h/ I+ H
3 `; m( |4 z& j# YquickSort(a, j+1, r); // 对右段排序

}
& ]' h& |# J3 s" l! k
  j8 M& g+ I% |2 F若把程序1 4 - 6中d o - w h i l e条件内的&lt;号和&gt;号分别修改为&lt; =和&gt; =，程序1 4 - 6仍然正确。实验结果表明使用程序1 4 - 6的快速排序代码可以得到比较好的平均性能。为了消除程序中的递归，必须引入堆栈。不过，消除最后一个递归调用不须使用堆栈。消除递归调用的工作留作练习（练习1 3）。程序1 4 - 6所需要的递归栈空间为O (n)。若使用堆栈来模拟递归，则可以把这个空间减少为O ( l o gn)。在模拟过程中，首先对left 和right 中较小者进行排序，把较大者的边界放入堆栈中。在最坏情况下l e f t总是为空，快速排序所需的计算时间为(n2 )。在最好情况下， l e f t和r i g h t中的元素数目大致相同，快速排序的复杂性为(nl o gn)。令人吃惊的是，快速排序的平均复杂性也是(nl o gn)。

定理2-1 快速排序的平均复杂性为(nl o gn)。
; ]+ d9 }/ Y  M% ?6 {* ?% p
7 _* g+ M- v' d5 d证明用t (n) 代表对含有n 个元素的数组进行排序的平均时间。当n≤1时，t (n)≤d，d为某一常数。当n &lt;1时，用s 表示左段所含元素的个数。由于在中段中有一个支点元素，因此右段中元素的个数为n-s- 1。所以左段和右段的平均排序时间分别为t (s), t (n-s- 1 )。分割数组中元素所需要的时间用cn 表示，其中c 是一个常数。因为s 有同等机会取0 ~n- 1中的任何一个值.
2 U+ ]( M+ q" ?* ^# J
: N! m. d9 @% c+ v* U% A( [2 W如对（2 - 8）式中的n 使用归纳法，可得到t (n)≤kn l o ge n，其中n&gt; 1且k=2(c+d)，e～2 . 7 1 8为自然对数的基底。在归纳开始时首先验证n= 2时公式的正确性。根据公式（ 1 4 - 8），可以得到t( 2 )≤2c+ 2d≤k nl o ge 2。在归纳假设部分，假定t(n)≤kn l o ge n（当2≤n＜m 时，m 是任意一个比2大的整数＝.

图1 4 - 1 0对本书中所讨论的算法在平均条件下和最坏条件下的复杂性进行了比较。
; ^4 _8 _) a) N" f% O$ t
3 D, ?* U! U8 K/ c6 X+ A' V* K: O
方法最坏复杂性平均复杂性
4 q/ A/ A9 g6 x- L$ D
8 p" T: s9 H0 O# ^- j6 x) R冒泡排序n2 n2
0 T; ~7 c2 d9 B( \% A% W
* K5 @' C$ T3 I( W. O2 a计数排序n2 n2

# J9 p  j" X7 w0 ^" S插入排序n2 n2
. Q$ B" ]( l; x* ]9 B
选择排序n2 n2
# s: E* b5 _, a; @/ h6 H2 @
+ y1 G# @- v  [堆排序nl o gn nl o gn

归并排序nl o gn nl o gn
5 W: C+ M% Q3 G" L/ [9 ]
快速排序n2 nl o gn

* l& T2 t  w8 g图14-10 各种排序算法的比较
6 f/ _* e1 x1 t. j; x) i$ ^

中值快速排序（ median-of-three quick sort）是程序1 4 - 6的一种变化，这种算法有更好的平均性能。注意到在程序1 4 - 6中总是选择a [ 1 ]做为支点，而在这种快速排序算法中，可以不必使用a [ 1 ]做为支点，而是取{a[1],a[(1+r)/2],a[r]} 中大小居中的那个元素作为支点。例如，假如有三个元素，大小分别为5，9，7，那么取7为支点。为了实现中值快速排序算法，一种最简单的方式就是首先选出中值元素并与a[1] 进行交换，然后利用程序1 4 - 6完成排序。如果a [ r ]是被选出的中值元素，那么将a[1] 与a[r] 进行交换，然后将a [ 1 ]（即原来的a [ r ]）赋值给程序1 4 - 6中的变量p i v o t，之后继续执行程序1 4 - 6中的其余代码。

图2 - 11中分别给出了根据实验所得到的归并排序、堆排序、插入排序、快速排序的平均时间。对于每一个不同的n, 都随机产生了至少1 0 0组整数。随机整数的产生是通过反复调用s t d l i b . h库中的r a n d o m函数来实现的。如果对一组整数进行排序的时间少于1 0个时钟滴答，则继续对其他组整数进行排序，直到所用的时间不低于1 0个时钟滴答。在图2 - 11中的数据包含产生随机整数的时间。对于每一个n，在各种排序法中用于产生随机整数及其他开销的时间是相同的。因此，图2 - 11中的数据对于比较各种排序算法是很有用的。
" e3 p8 r4 q: b6 K6 J9 ?
  Q7 b8 `' a- H, @. ], c对于足够大的n，快速排序算法要比其他算法效率更高。从图中可以看到快速排序曲线与插入排序曲线的交点横坐标比2 0略小，可通过实验来确定这个交点横坐标的精确值。可以分别用n = 1 5 , 1 6 , 1 7 , 1 8 , 1 9进行实验，以寻找精确的交点。令精确的交点横坐标为nBr e a k。当n≤nBreak 时，插入排序的平均性能最佳。当n＞nBreak 时，快速排序性能最佳。当n＞nBreak 时，把插入排序与快速排序组合为一个排序函数，可以提高快速排序的性能，实现方法是把程序1 4 - 6中的以下语句：
  y! J7 R% ^% l# [
if(l &gt;= r)r e t u r n ;
6 ]4 P: M% g, q0 |% `$ [
6 U4 Z* g. Z+ o替换为
, Q: w( j% o: E8 ]5 u* ^
if (r-1<NBREAK) {InsertionSort(a,l,r); return;}
" N/ [$ P  b9 x3 b* `
9 K) H# k# i; a! ~9 K5 A( P/ A这里I n s e r t i o n S o r t ( a , l , r )用来对a [ 1 : r ]进行插入排序。测量修改后的快速排序算法的性能留作练习（练习2 0）。用更小的值替换n B r e a k有可能使性能进一步提高（见练习2 0）。
% H& N" _1 V) B& [0 C) L  c$ _
大多数实验表明，当n＞c时（c为某一常数），在最坏情况下归并排序的性能也是最佳的。而当n≤c时，在最坏情况下插入排序的性能最佳。通过将插入排序与归并排序混合使用，可以提高归并排序的性能（练习2 1）。</P>