选择排序

韩冰

<>对于给定的n 个元素的数组a [ 0 : n - 1 ]，要求从中找出第k小的元素。当a [ 0 : n - 1 ]被排序时，该元素就是a [ k - 1 ]。假设n = 8，每个元素有两个域k e y和I D，其中k e y是一个整数，I D是一个字符。假设这8个元素为[ ( 1 2 ,a)，( 4 ,b)，( 5 ,c)，( 4 ,d)，( 5 ,e)，( 1 0 ,f)，( 2 ,g)，( 2 0 ,h)], 排序后得到数组[ ( 2 ,g)，( 4 ,d)，( 4 ,b)，( 5 ,c)，( 5 ,e)，( 1 0 ,f)，( 1 2 ,a)，( 2 0 ,h) ]。如果k = 1，返回I D为g 的元素；如果k = 8，返回I D为h 的元素；如果k = 6，返回是I D为f 的元素；如果k = 2，返回I D为d 的元素。实际上，对最后一种情况，所得到的结果可能不唯一，因为排序过程中既可能将I D为d 的元素排在a [ 1 ]，也可能将I D为b 的元素排在a [ 1 ]，原因是它们具有相同大小的k e y，因而两个元素中的任何一个都有可能被返回。但是无论如何，如果一个元素在k = 2时被返回，另一个就必须在k = 3时被返回。
# Q8 f/ l' Z0 O
4 T! u+ g* R8 i选择问题的一个应用就是寻找中值元素，此时k = [n / 2 ]。中值是一个很有用的统计量，例如中间工资，中间年龄，中间重量。其他k值也是有用的。例如，通过寻找第n / 4 , n / 2和3 n / 4这三个元素,可将人口划分为4份。
' a) ?9 s. j* X8 Q* C
) K& z+ T( ^8 B% Q/ Q4 w7 z0 J* F& M选择问题可在O ( n l o g n )时间内解决，方法是首先对这n个元素进行排序（如使用堆排序式或归并排序），然后取出a [ k - 1 ]中的元素。若使用快速排序（如图1 4 - 11所示），可以获得更好的平均性能，尽管该算法有一个比较差的渐近复杂性O( n2 )。

/ g- g+ F$ j8 {可以通过修写程序1 4 - 6来解决选择问题。如果在执行两个w h i l e循环后支点元素a [ l ]被交换到a [ j ] ,那么a [ l ]是a [ l : j ]中的第j - l + 1个元素。如果要寻找的第k 个元素在a [ l : r ]中，并且j - l + 1等于k，则答案就是a [ l ]；如果j - l + 1 &lt; k，那么寻找的元素是r i g h t中的第k - j + l - 1个元素，否则要寻找的元素是left 中的第k个元素。因此，只需进行0次或1次递归调用。新代码见程序1 4 - 7。S e l e c t中的递归调用可用f o r或w h i l e循环来替代（练习2 5）。

程序14-7 寻找第k 个元素
% ]  A; x$ [( g# |6 L
template<CLASS T>

T Select(T a[], int n, int k)

{// 返回a [ 0 : n - 1 ]中第k小的元素
) l# B' x/ ?+ H/ O
% k" j' _+ G5 ^& {# [8 G& ?, r// 假定a[n] 是一个伪最大元素
3 Z7 r9 L0 f  ?8 }
0 l0 E6 z. P: X, x: ?- r) z( Oif (k &lt; 1 || k &gt; n) throw OutOfBounds();
" j* d  U* ~1 P; Q- e
# B2 g/ D0 j; }& S: M9 i3 v) ireturn select(a, 0, n-1, k);
# H3 k; c# {; q) g+ O+ x
; e) s5 A; D- n# T}
3 J  o$ }0 j. o+ k/ |; i1 Y
template<CLASS T>

$ N+ q# l0 V% P  H4 H/ A6 sT select(T a[], int l, int r, int k)

8 e- {" J' M4 E  E* q% Z9 K{// 在a [ l : r ]中选择第k小的元素
% w: s4 H9 B& }; o3 ~% l9 Y
if (l &gt;= r) return a[l];

int i = l, // 从左至右的游标
1 ^  E# P/ G9 ?. Z8 M0 P
j = r + 1; // 从右到左的游标
2 Z5 V5 V: _7 ]& x% u
& m) q6 S- z+ V5 ?; |0 c/ vT pivot = a[l];

0 a% N* D- ]/ N2 ]# i# z/ R# o// 把左侧&gt;= pivot的元素与右侧&lt;= pivot 的元素进行交换

while (true) {

! Q; i! ]: n& `. b: Edo {// 在左侧寻找&gt;= pivot 的元素

$ e. D, R- e5 g5 Ri = i + 1;
9 X) e( \+ u, o$ w+ M
( l7 \9 d( y$ x0 p: O; _} while (a &lt; pivot);

4 [3 k4 g1 f  w8 Z! y! s0 D0 w" [do {// 在右侧寻找&lt;= pivot 的元素
" {* h7 m- @/ }  ~  V7 x0 N# G
5 ]' b7 [3 c+ W+ \j = j - 1;
, b2 W1 _# g) d+ x
} while (a[j] &gt; pivot);
+ z" R  }6 [1 f& x2 s- ]/ U) T& {
/ p( ?( O, _5 ~" _6 Y- xif (i &gt;= j) break; // 未发现交换对象
2 x) e; a4 \4 Q. Y# q3 |
2 `& P7 b6 U2 ASwap(a, a[j]);

8 u/ g1 h% c" V* @& u1 @}

if (j - l + 1 == k) return pivot;
9 i/ O! Z, d8 v; l2 I
. S& r4 P2 f0 ^// 设置p i v o t
* \& G! i" p5 O; m
a[l] = a[j];
* `; Z8 P: k5 x
a[j] = pivot;

! [) I4 q2 }. E$ M: f: J5 [// 对一个段进行递归调用
1 J& |- L" Z4 `6 I- V; A
if (j - l + 1 &lt; k)
) W5 j& i* k2 S' k3 q4 y
9 R+ n( I7 D8 r, w! r9 areturn select(a, j+1, r, k-j+l-1);
7 g8 I3 \. i9 ^* C% H4 s% z& r
else return select(a, l, j-1, k);

5 c% t, |  u: Q8 ~}
  l' A, R2 M; K2 S% u$ D
程序1 4 - 7在最坏情况下的复杂性是( n2 )，此时left 总是为空，而且第k个元素总是位于r i g h t.
0 Z# V$ }. ^% H: P5 r9 }* O
6 y  H9 I+ d; x( S9 L  S如果假定n 是2的幂，则可以取消公式（2 - 1 0）中的向下取整操作符。通过使用迭代方法，可以得到t (n) = (n)。若仔细地选择支点元素，则最坏情况下的时间开销也可以变成(n)。一种选择支点元素的方法是使用“中间的中间（ m e d i a n - o f - m e d i a n）”规则，该规则首先将数组a中的n 个元素分成n/r 组，r 为某一整常数，除了最后一组外，每组都有r 个元素。然后通过在每组中对r 个元素进行排序来寻找每组中位于中间位置的元素。最后根据所得到的n/r 个中间元素，递归使用选择算法，求得所需要的支点元素。

例2-6 [中间的中间] 考察如下情形：r=5, n=27, 并且a= [ 2，6，8，1，4，1 0，2 0，6，2 2，11，9，8，4，3，7，8，1 6，11，1 0，8，2，1 4，1 5，1，1 2，5，4 ]。这2 7个元素可以被分为6组[ 2 , 6 , 8 , 1 , 4 ]，[ 1 0 , 2 0 , 6 , 2 2 , 11 ]，[ 9 , 8 , 4 , 3 , 7 ]，[ 8 , 1 6 , 11 , 1 0 , 8 ]，[ 2 , 1 4 , 1 5 , 1 , 1 2 ]和[ 5 , 4 ]，每组的中间元素分别为4 , 11 , 7 , 1 0 , 1 2和4。[ 4 , 11 , 7 , 1 0 , 1 2 , 4 ]的中间元素为7。这个中间元素7被取为支点元素。由此可以得到l e ft= [ 2 , 6 , 1 , 4 , 6 , 4 , 3 , 2 , 1 , 5 , 4 ]，m i d d l e= [ 7 ] ,r i g h t= [ 8 , 1 0 , 2 0 , 2 2 , 11 , 9 , 8 , 8 , 1 6 , 11 , 1 0 , 8 , 1 4 , 1 5 , 1 2 ]。
; H' @' O3 Z. P- h5 w/ o) u/ m6 O
) l9 T! B+ Y8 ^9 h# v1 l6 o3 ^如果要寻找第k个元素且k&lt; 1 2，则仅仅需要在l e f t中寻找；如果k= 1 2，则要找的元素就是支点元素；如果k&gt; 1 2，则需要检查r i g h t中的1 5个元素。在最后一种情况下，需在r i g h t中寻找第(k- 1 2 )个元素。

! }* g% P/ Q  h  d4 k/ `7 e4 I定理2-2 当按“中间的中间”规则选取支点元素时，以下结论为真：
5 M) f: |# F3 a. j( J; z, R& J1 C
1) 若r=9, 那么当n≥9 0时，有m a x { |l e f e|, |r i g h t| }≤7n / 8。
; T+ ]3 ^/ y2 c# X5 Z
& N4 d/ }3 H- O1 x) P7 f5 Q2) 若r= 5，且a 中所有元素都不同，那么当n≥2 4时，有max{| left |, | right | }≤3n/ 4。
" z$ X( I) l- E* g9 A
! `; F  z- q% f+ H; u: ^9 g  @证明这个定理的证明留作练习2 3。

+ d1 U2 S2 W$ u根据定理2 - 2和程序1 4 - 7可知，如果采用“中间的中间”规则并取r= 9，则用于寻找第k个元素的时间t (n)可按如下递归公式来计算：
: A* m) B, s' l/ C* k1 P8 B
在上述递归公式中，假设当n＜9 0时使用复杂性为nl o gn的求解算法，当n≥9 0时，采用“中间的中间”规则进行分而治之求解。利用归纳法可以证明，当n≥1时有t (n)≤7 2cn (练习2 4 )。

当元素互不相同时，可以使用r= 5来得到线性时间性能。</P>