算法導論-順序統計
目錄
1、問題的引出-求第i個順序統計量
2、方法一：以期望線性時間做選擇
3、方法二（改進）：最壞情況線性時間的選擇
4、完整測試代碼（c++）
5、參考資料
內容
1、問題的引出-求第i個順序統計量
什麼是順序統計量？及中位數概念
在一個由元素組成的集合裡，第i個順序統計量（order statistic）是該集合第i小的元素。例如，最小值是第1個順序統計量(i=1)，最大值是第n個順序統計量(i=n)。一個中位數（median）是它所在集合的“中點元素”。當n為奇數時，中位數是唯一的；當n為偶數時，中位數有兩個。問題簡單的說就是：求數組中第i小的元素。
那麼問題來了：如何求一個數組裡第i小的元素呢？
常規方法：可以首先進行排序，然後取出中位數。由於排序算法（快排，堆排序，歸並排序）效率能做到Θ(nlogn),所以，效率達不到線性； 在本文中將介紹兩種線性的算法，第一種期望效率是線性的，第二種效率較好，是在最壞情況下能做到線性效率。見下面兩個小節；
2、方法一：以期望線性時間做選擇
這是一種分治算法：以快速排序為模型：隨機選取一個主元，把數組劃分為兩部分，A[p...q-1]的元素比A[q]小，A[q+1...r]的元素比A[q]大。與快速排序不同，如果i=q，則A[q]就是要找的第i小 的元素，返回這個值；如果i < q，則說明第i小的元素在A[p...q-1]裡；如果i > q，則說明第i小的元素在A[q+1...r]裡；然後在上面得到的高區間或者低區間裡進行遞歸求取，直到找到第i小的元素。
下面是在A[p...q]中找到第i小元素的偽碼：
復制代碼
1 RandomSelect(A,p, q,k)//隨機選擇統計，以期望線性時間做選擇
2 {
3 if (p==q) return A[p];
4 int pivot=Random_Partition(A,p,q);//隨機選擇主元，把數組進行劃分為兩部分
5 int i=pivot-p+1;
6 if (i==k )return A[pivot];
7 else if (i<k) return RandomSelect(A,pivot+1,q,k-i);//第k小的數不在主元左邊，則在右邊遞歸選擇
8 else return RandomSelect(A,p,pivot-1,k);//第k小的數不在主元右邊，則在左邊遞歸選擇
9 }
復制代碼
在最壞情況下，數組被劃分為n-1和0兩部分，而第i個元素總是落在n-1的那部分裡，運行時間為Ө(n^2);但是，除了上述很小的概率情況，其他情況都能達到線性；在平均情況下，任何順序統計量都可以在線性時間Θ(n)內得到。
實現代碼（c++）：
1 //template<typename T>使用模板，可處理任意類型的數據
2 template<typename T>//交換數據
3 void Swap(T &m,T &n)
4 {
5 T tmp;
6 tmp=m;
7 m=n;
8 n=tmp;
9 }
10
11 /***********隨機快速排序分劃程序*************/
12 template<typename T>
13 int Random_Partition(vector<T> &A,int p,int q)
14 {
15 //隨機選擇主元，與第一個元素交換
16 srand(time(NULL));
17 int m=rand()%(q-p+1)+p;
18 Swap(A[m],A[p]);
19 //下面與常規快排劃分一樣
20 T x=A[p];
21 int i=p;
22 for (int j=p+1;j<=q;j++)
23 {
24 if (A[j]<x)
25 {
26 i=i+1;
27 Swap(A[i],A[j]);
28 }
29 }
30 Swap(A[p],A[i]);
31 return i;
32 }
33 /***********隨機選擇統計函數*************/
34 template<typename T>
35 T RandomSelect(vector<T> &A,int p,int q,int k)//隨機選擇統計，以期望線性時間做選擇
36 {
37 if (p==q) return A[p];
38 int pivot=Random_Partition(A,p,q);//隨機選擇主元，把數組進行劃分為兩部分
39 int i=pivot-p+1;
40 if (i==k )return A[pivot];
41 else if (i<k) return RandomSelect(A,pivot+1,q,k-i);//第k小的數不在主元左邊，則在右邊遞歸選擇
42 else return RandomSelect(A,p,pivot-1,k);//第k小的數不在主元右邊，則在左邊遞歸選擇
43 }
復制代碼
3、方法二（改進）：最壞情況線性時間的選擇
相比於上面的隨機選擇，我們有另一種類似的算法，它在最壞情況下也能達到O(n)。它也是基於數組的劃分操作，而且利用特殊的手段保證每次劃分兩邊的子數組都比較平衡；與上面算法不同之處是：本算法不是隨機選擇主元，而是采取一種特殊的方法選擇“中位數”，這樣能使子數組比較平衡，避免了上述的最壞情況（Ө(n^2)）。選出主元後，後面的處理和上述算法一致。
那麼問題又來了，這種特殊的手段是什麼呢？
如上圖所示：
1） 將輸入數組的n個元素劃分為n/5組，每組（上圖中的每列為一組）5個元素，且至多只有一個組有剩下的n%5個元素組成
2） 首先對每組中的元素（5個）進行插入排序，然後從排序後的序列中選擇出中位數（圖中黃色數）。
3） 對第2步中找出的n/5個中位數，遞歸調用SELECT以找出其中位數x（圖中紅色數）。（如果有偶數個中位數取較小的中位數）
這三個步驟就可以選出一個很好的主元，下面的處理和方法一一致（遞歸）
OK! 下面是完整的算法步驟：
1） 將輸入數組的n個元素劃分為n/5組，每組（上圖中的每列為一組）5個元素，且至多只有一個組有剩下的n%5個元素組成
2） 首先對每組中的元素（5個）進行插入排序，然後從排序後的序列中選擇出中位數（圖中黃色數）。
3） 對第2步中找出的n/5個中位數，遞歸調用SELECT以找出其中位數x（圖中紅色數）。（如果有偶數個中位數取較小的中位數）
4） 調用PARTITION過程，按照中位數x對輸入數組進行劃分。確定中位數x的位置k。
5） 如果i=k，則返回x。否則，如果i<k，則在地區間遞歸調用SELECT以找出第i小的元素，若干i>k，則在高區找第(i-k)個最小元素。
大致偽碼：
復制代碼
1 WorseLinearSelect(vector<T> &A,int p,int q,int k)
2 {
3 // 將輸入數組的n個元素劃分為n/5（上取整）組，每組5個元素，
4 // 且至多只有一個組有剩下的n%5個元素組成。
5 if (p==q) return A[p];
6
7 int len=q-p+1;
8 int medianCount=1;
9 if (len>5)
10 medianCount = len%5 >0 ? len/5 + 1 : len/5;
11 vector<T> medians(medianCount);//存放每組的中位數
12
13 // 尋找每個組的中位數。首先對每組中的元素（至多為5個）進行插入排序，
14 // 然後從排序後的序列中選擇出中位數。
15 int m=p;
16 for (int j=0,m=p;j<medianCount-1;j++)
17 {
18 medians[j] = GetMedian(A,m,m+4);
19 m+=5;
20 }
21 medians[medianCount-1] = GetMedian(A,m,q);
22 //對第2步中找出的n/5（上取整）個中位數，遞歸調用SELECT以找出其中位數pivot。
23 //（如果是偶數去下中位數）
24 int pivot = WorseLinearSelect(medians,0,medianCount-1,(medianCount+1)/2);
25 //調用PARTITION過程，按照中位數pivot對輸入數組進行劃分。確定中位數pivot的位置r。
26 int r = partitionWithPivot(A,p,q,pivot);
27 int num = r-p+1;
28 //如果num=k，則返回pivot。否則，如果k<num，則在地區間遞歸調用SELECT以找出第k小的元素，
29 //若干k>num，則在高區找第(k-num)個最小元素。
30 if(num==k) return pivot;
31 else if (num>k) return WorseLinearSelect(A,p,r-1,k);
32 else return WorseLinearSelect(A,r+1,q,k-num);
33 }
復制代碼
該算法在最壞情況下運行時間為Θ(n)
代碼實現(c++)：
1 template<typename T>//插入排序
2 void insertion_sort(vector<T> &A,int p,int q)
3 {
4 int i,j;
5 T key;
6 int len=q-p+1;
7 for (j=p+1;j<=q;j++)
8 {
9 i=j-1;
10 key=A[j];
11 while (i>=p&&A[i]>key)
12 {
13 A[i+1]=A[i];
14 i--;
15 }
16 A[i+1]=key;
17 }
18 }
19 /*
20 * 利用插入排序選擇中位數
21 */
22 template<typename T>
23 T GetMedian(vector<T> &A,int p,int q)
24 {
25 insertion_sort(A,p,q);//插入排序
26 return A[(q-p)/2 + p];//返回中位數,有兩個中位數的話返回較小的那個
27 }
28 /*
29 * 根據指定的劃分主元pivot來劃分數組
30 * 並返回主元的順序位置
31 */
32 template<typename T>
33 int partitionWithPivot(vector<T> &A,int p,int q,T piovt)
34 {
35 //先把主元交換到數組首元素
36 for (int i=p;i<q;i++)
37 {
38 if (A[i] == piovt)
39 {
40 Swap(A[i],A[p]);
41 break;
42 }
43 }
44 //常規的快速排序劃分程序
45 //
46 T x=A[p];
47 int i=p;
48 for (int j=p+1;j<=q;j++)
49 {
50 if (A[j]<x)
51 {
52 i=i+1;
53 Swap(A[i],A[j]);
54 }
55 }
56 Swap(A[p],A[i]);
57 return i;
58 }
59 /*
60 * 最壞情況下線性時間選擇算法
61 * 此算法依然是建立在快速排序的劃分算法基礎之上的
62 * 但是與randomizedSelect算法的不同指之處，就是次算法的本質
63 * 是保證了每次劃分選擇的劃分主元一定是一個較好的主元，算法先對數組5個一組進行分組
64 * 然後選擇每組的中位數，再遞歸的選擇各組中位數中的中位數作為數組的劃分主元，以此保證劃分的平衡性
65 * 選擇中位數的時候必須使用遞歸調用的方法才能降低時間復雜度
66 * 從而保證在最壞情況下都得到一個好的劃分
67 * 最壞情況下時間復雜度為O(n)
68 */
69 template<typename T>
70 T WorseLinearSelect(vector<T> &A,int p,int q,int k)
71 {
72 // 將輸入數組的n個元素劃分為n/5（上取整）組，每組5個元素，
73 // 且至多只有一個組有剩下的n%5個元素組成。
74 if (p==q) return A[p];
75
76 int len=q-p+1;
77 int medianCount=1;
78 if (len>5)
79 medianCount = len%5 >0 ? len/5 + 1 : len/5;
80 vector<T> medians(medianCount);//存放每組的中位數
81
82 // 尋找每個組的中位數。首先對每組中的元素（至多為5個）進行插入排序，
83 // 然後從排序後的序列中選擇出中位數。
84 int m=p;
85 for (int j=0,m=p;j<medianCount-1;j++)
86 {
87 medians[j] = GetMedian(A,m,m+4);
88 m+=5;
89 }
90 medians[medianCount-1] = GetMedian(A,m,q);
91 //對第2步中找出的n/5（上取整）個中位數，遞歸調用SELECT以找出其中位數pivot。
92 //（如果是偶數去下中位數）
93 int pivot = WorseLinearSelect(medians,0,medianCount-1,(medianCount+1)/2);
94 //調用PARTITION過程，按照中位數pivot對輸入數組進行劃分。確定中位數pivot的位置r。
95 int r = partitionWithPivot(A,p,q,pivot);
96 int num = r-p+1;
97 //如果num=k，則返回pivot。否則，如果k<num，則在地區間遞歸調用SELECT以找出第k小的元素，
98 //若干k>num，則在高區找第(k-num)個最小元素。
99 if(num==k) return pivot;
100 else if (num>k) return WorseLinearSelect(A,p,r-1,k);
101 else return WorseLinearSelect(A,r+1,q,k-num);
102 }
復制代碼
4、完整測試代碼（c++）
Select.h
復制代碼
1 #ifndef SELECT_HH
2 #define SELECT_HH
3 template<typename T>
4 class Select
5 {
6 public:
7 T RandomSelect(vector<T> &A,int p,int q,int k);//期望線性時間做選擇
8 T WorseLinearSelect(vector<T> &A,int p,int q,int k);//最壞情況線性時間的選擇
9 private:
10 void Swap(T &m,T &n);//交換數據
11 int Random_Partition(vector<T> &A,int p,int q);//隨機快排分劃
12 void insertion_sort(vector<T> &A,int p,int q);//插入排序
13 T GetMedian(vector<T> &A,int p,int q);
14 int partitionWithPivot(vector<T> &A,int p,int q,T piovt);//根據指定主元pivot來劃分數據並返回主元的順序位置
15 };
16
17 template<typename T>//交換數據
18 void Select<T>::Swap(T &m,T &n)
19 {
20 T tmp;
21 tmp=m;
22 m=n;
23 n=tmp;
24 }
25
26 /***********隨機快速排序分劃程序*************/
27 template<typename T>
28 int Select<T>::Random_Partition(vector<T> &A,int p,int q)
29 {
30 //隨機選擇主元，與第一個元素交換
31 srand(time(NULL));
32 int m=rand()%(q-p+1)+p;
33 Swap(A[m],A[p]);
34 //下面與常規快排劃分一樣
35 T x=A[p];
36 int i=p;
37 for (int j=p+1;j<=q;j++)
38 {
39 if (A[j]<x)
40 {
41 i=i+1;
42 Swap(A[i],A[j]);
43 }
44 }
45 Swap(A[p],A[i]);
46 return i;
47 }
48 /***********隨機選擇統計函數*************/
49 template<typename T>
50 T Select<T>::RandomSelect(vector<T> &A,int p,int q,int k)//隨機選擇統計，以期望線性時間做選擇
51 {
52 if (p==q) return A[p];
53 int pivot=Random_Partition(A,p,q);//隨機選擇主元，把數組進行劃分為兩部分
54 int i=pivot-p+1;
55 if (i==k )return A[pivot];
56 else if (i<k) return RandomSelect(A,pivot+1,q,k-i);//第k小的數不在主元左邊，則在右邊遞歸選擇
57 else return RandomSelect(A,p,pivot-1,k);//第k小的數不在主元右邊，則在左邊遞歸選擇
58 }
59
60 template<typename T>//插入排序
61 void Select<T>::insertion_sort(vector<T> &A,int p,int q)
62 {
63 int i,j;
64 T key;
65 int len=q-p+1;
66 for (j=p+1;j<=q;j++)
67 {
68 i=j-1;
69 key=A[j];
70 while (i>=p&&A[i]>key)
71 {
72 A[i+1]=A[i];
73 i--;
74 }
75 A[i+1]=key;
76 }
77 }
78 /*
79 * 利用插入排序選擇中位數
80 */
81 template<typename T>
82 T Select<T>::GetMedian(vector<T> &A,int p,int q)
83 {
84 insertion_sort(A,p,q);//插入排序
85 return A[(q-p)/2 + p];//返回中位數,有兩個中位數的話返回較小的那個
86 }
87 /*
88 * 根據指定的劃分主元pivot來劃分數組
89 * 並返回主元的順序位置
90 */
91 template<typename T>
92 int Select<T>::partitionWithPivot(vector<T> &A,int p,int q,T piovt)
93 {
94 //先把主元交換到數組首元素
95 for (int i=p;i<q;i++)
96 {
97 if (A[i] == piovt)
98 {
99 Swap(A[i],A[p]);
100 break;
101 }
102 }
103 //常規的快速排序劃分程序
104 //
105 T x=A[p];
106 int i=p;
107 for (int j=p+1;j<=q;j++)
108 {
109 if (A[j]<x)
110 {
111 i=i+1;
112 Swap(A[i],A[j]);
113 }
114 }
115 Swap(A[p],A[i]);
116 return i;
117 }
118 /*
119 * 最壞情況下線性時間選擇算法
120 * 此算法依然是建立在快速排序的劃分算法基礎之上的
121 * 但是與randomizedSelect算法的不同指之處，就是次算法的本質
122 * 是保證了每次劃分選擇的劃分主元一定是一個較好的主元，算法先對數組5個一組進行分組
123 * 然後選擇每組的中位數，再遞歸的選擇各組中位數中的中位數作為數組的劃分主元，以此保證劃分的平衡性
124 * 選擇中位數的時候必須使用遞歸調用的方法才能降低時間復雜度
125 * 從而保證在最壞情況下都得到一個好的劃分
126 * 最壞情況下時間復雜度為O(n)
127 */
128 template<typename T>
129 T Select<T>::WorseLinearSelect(vector<T> &A,int p,int q,int k)
130 {
131 // 將輸入數組的n個元素劃分為n/5（上取整）組，每組5個元素，
132 // 且至多只有一個組有剩下的n%5個元素組成。
133 if (p==q) return A[p];
134
135 int len=q-p+1;
136 int medianCount=1;
137 if (len>5)
138 medianCount = len%5 >0 ? len/5 + 1 : len/5;
139 vector<T> medians(medianCount);//存放每組的中位數
140
141 // 尋找每個組的中位數。首先對每組中的元素（至多為5個）進行插入排序，
142 // 然後從排序後的序列中選擇出中位數。
143 int m=p;
144 for (int j=0,m=p;j<medianCount-1;j++)
145 {
146 medians[j] = GetMedian(A,m,m+4);
147 m+=5;
148 }
149 medians[medianCount-1] = GetMedian(A,m,q);
150 //對第2步中找出的n/5（上取整）個中位數，遞歸調用SELECT以找出其中位數pivot。
151 //（如果是偶數去下中位數）
152 int pivot = WorseLinearSelect(medians,0,medianCount-1,(medianCount+1)/2);
153 //調用PARTITION過程，按照中位數pivot對輸入數組進行劃分。確定中位數pivot的位置r。
154 int r = partitionWithPivot(A,p,q,pivot);
155 int num = r-p+1;
156 //如果num=k，則返回pivot。否則，如果k<num，則在地區間遞歸調用SELECT以找出第k小的元素，
157 //若干k>num，則在高區找第(k-num)個最小元素。
158 if(num==k) return pivot;
159 else if (num>k) return WorseLinearSelect(A,p,r-1,k);
160 else return WorseLinearSelect(A,r+1,q,k-num);
161 }
162 #endif
復制代碼
main.cpp
復制代碼
1 #include <iostream>
2 #include <vector>
3 #include <time.h>
4 using namespace std;
5 #include "Select.h"
6 #define N 10 //排序數組大小
7 #define K 100 //排序數組范圍0～K
8 ////打印數組
9 void print_element(vector<int> A)
10 {
11 int len=A.size();
12 for (int i=0;i<len;i++)
13 {
14 std::cout<<A[i]<<" ";
15 }
16 std::cout<<std::endl;
17 }
18 int main()
19 {
20 Select <int> s1;
21 int a[10]={23,4,34,345,3,21,45,246,98,50};
22 vector<int> vec_int(a,a+10);
23 cout<<"原始數組"<<endl;
24 print_element(vec_int);
25 // 期望線性時間做選擇測試
26 cout<<"期望線性時間做選擇測試"<<endl;
27 for(int i=1;i<=N;i++)
28 {
29 int kMin=s1.RandomSelect(vec_int,0,N-1,i);
30 cout<<"第"<<i<<"小的數是："<<kMin<<endl;
31 }
32 //最壞情況線性時間的選擇測試
33 cout<<"最壞情況線性時間的選擇測試"<<endl;
34 for(int i=1;i<=N;i++)
35 {
36 int kMin=s1.WorseLinearSelect(vec_int,0,N-1,i);
37 cout<<"第"<<i<<"小的數是："<<kMin<<endl;
38 }
39 system("PAUSE");
40 return 0;
41 }
