《算法导论》学习总结 — 9.第九章 中位数和顺序统计学
这一章的内容很简单，基本都是一些概念。
第i个顺序统计量:在一个由n个元素组成的集合中，第i个顺序统计量(order statistic)是该集合中第i小的元素。
最小值是第1个顺序统计量(i=1)
最大值是第n个顺序统计量(i=n)
中位数：一个中位数(median)是它所在集合的“中点元素”，当n为奇数时，i=(n+1)/2，当n为偶数是，中位数总是出现在 （下中位数）和 （上中位数）。
找最大值/最小值问题，通过比较n-1次可以得出结果。
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 如果要同时找出最大值和最小值，则比较次数最少并不是2*n-2，而是，我们可以将一对元素比较，然后把较大者于max比较，较小者与min比较，这样就只需要。
如果是一般的选择问题，即找出一段序列第i小的数，看起来要比找最大值或最小值要麻烦，其实两种问题的渐进时间都是 。首先看看这个强悍的伪代码：
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)
这个算法利用了随机化的Partition算法，这个实在第七章的随机化快排中讲到：http://www.wutianqi.com/?p=2368，不记得的可以先复习下前面的快排。这个随机化的选择算法返回数组A[p..r]中第i小的元素。
具体实现如下：
1 /*
2 Author: Tanky Woo
3 Blog: www.WuTianQi.com
4 About: 《算法导论》第9章 查找序列第i小的数字
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小的数字是: " << ith << endl;
61 getchar();
62
63 return 0;
64 }
结果如图：
在(89, 100, 21, 5, 2, 8, 33, 27, 63)中查找第二小的数字是5.该算法的平均情况性能较好，并且又是随机化的，所有没有哪一种特别的输入会导致最坏情况发生。
补充：综合编程 , 其他综合 ,
