建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
這一章的內(nèi)容很簡(jiǎn)單，基本都是一些概念。
第i個(gè)順序統(tǒng)計(jì)量:在一個(gè)由n個(gè)元素組成的集合中，第i個(gè)順序統(tǒng)計(jì)量(order statistic)是該集合中第i小的元素。
最小值是第1個(gè)順序統(tǒng)計(jì)量(i=1)
最大值是第n個(gè)順序統(tǒng)計(jì)量(i=n)
中位數(shù)：一個(gè)中位數(shù)(median)是它所在集合的“中點(diǎn)元素”，當(dāng)n為奇數(shù)時(shí)，i=(n+1)/2，當(dāng)n為偶數(shù)是，中位數(shù)總是出現(xiàn)在
（下中位數(shù)）和
（上中位數(shù)）。
找最大值/最小值問(wèn)題，通過(guò)比較n-1次可以得出結(jié)果。
MINIMUM(A)
1 min ← A[1]
2 for i ← 2 to length[A]
3 do if min > A[i]
4 then min ← A[i]
5 return min
如果要同時(shí)找出最大值和最小值，則比較次數(shù)最少并不是2*n-2，而是
，我們可以將一對(duì)元素比較，然后把較大者于max比較，較小者與min比較，這樣就只需要
。
如果是一般的選擇問(wèn)題，即找出一段序列第i小的數(shù)，看起來(lái)要比找最大值或最小值要麻煩，其實(shí)兩種問(wèn)題的漸進(jìn)時(shí)間都是
。
首先看看這個(gè)強(qiáng)悍的偽代碼：
RANDOMIZED-SELECT(A, p, r, i)
1 if p = r
2 then return A[p]
3 q ← RANDOMIZED-PARTITION(A, p, r)
4 k ← q - p + 1
5 if i = k ? the pivot value is the answer
6 then return A[q]
7 elseif i < k
8 then return RANDOMIZED-SELECT(A, p, q - 1, i)
9 else return RANDOMIZED-SELECT(A, q + 1, r, i - k)
這個(gè)算法利用了隨機(jī)化的Partition算法，這個(gè)實(shí)在第七章的隨機(jī)化快排中講到：http://www.wutianqi.com/?p=2368，不記得的可以先復(fù)習(xí)下前面的快排。
這個(gè)隨機(jī)化的選擇算法返回?cái)?shù)組A[p..r]中第i小的元素。
具體實(shí)現(xiàn)如下：
1 /*
2 Author: Tanky Woo
3 Blog: www.WuTianQi.com
4 About: 《算法導(dǎo)論》第9章 查找序列第i小的數(shù)字
5 */
6
7 #include <iostream>
8 #include <cstdlib>
9 using namespace std;
10
11 int Partition(int *arr, int beg, int end)
12 {
13 int sentinel = arr[end];
14 int i = beg-1;
15 for(int j=beg; j<=end-1; ++j)
16 {
17 if(arr[j] <= sentinel)
18 {
19 i++;
20 swap(arr[i], arr[j]);
21 }
22 }
23 swap(arr[i+1], arr[end]);
24
25 return i+1;
26 }
27
28 int RandomPartition(int *arr, int beg, int end)
29 {
30 int i = beg + rand() % (end-beg+1);
31 swap(arr[i], arr[end]);
32 return Partition(arr, beg, end);
33 }
34
35
36 int RandomSelect(int *a, int p, int r, int i)
37 {
38 if(p == r)
39 return a[p];
40 int q = Partition(a, p, r);
41 int k = q-p+1;
42 if(i == k)
43 return a[q];
44 else if(i < k)
45 return RandomSelect(a, p, q-1, i);
46 else
47 return RandomSelect(a, q+1, r, i-k);
48 }
49
50 int main()
51 {
52 int a[] = {0, 89, 100, 21, 5, 2, 8, 33, 27, 63};
53 int num = 9;
54 int ith;
55 cout << "序列為: ";
56 for(int i=1; i<=num; ++i)
57 cout << a[i] << " ";
58 cout << endl;
59 ith = RandomSelect(a, 1, num, 2);
60 cout << "序列中第2小的數(shù)字是: " << ith << endl;
61 getchar();
62
63 return 0;
64 }
結(jié)果如圖：
在(89, 100, 21, 5, 2, 8, 33, 27, 63)中查找第二小的數(shù)字是5.
該算法的平均情況性能較好，并且又是隨機(jī)化的，所有沒(méi)有哪一種特別的輸入會(huì)導(dǎo)致最壞情況發(fā)生。
在我獨(dú)立博客上的原文：
http://www.wutianqi.com/?p=2395歡迎大家互相學(xué)習(xí)，互相探討。
posted on 2011-04-26 13:00
Tanky Woo 閱讀(1571)
評(píng)論(1) 編輯 收藏 引用