/*
* Order Statistics 順序統計
* Select(int* a, int n, int ith): 從給定的n個元素中找出第i個小的元素
* 思想：QuickSort的Partition方法進行分割
* 如果 i = rank(pivot), 則返回a[k]
* 如果 i < rank(pivot), 則從前半部分中找第i個小的元素
* 如果 i > rank(pivot), 則從后半部分中找第i-rank(pivot)個小的元素
* 最壞運行時間O(n^2)
* 平均運行時間O(nlgn)
*/
1
#include <iostream>
2#include <cstdlib>
3
4using namespace std;
5
6//交換兩個元素值
7void swap(int& a , int& b)
8
{
9
int temp = a;
10 a = b;
11 b = temp;
12
}
13
14//輸出數組
15void print(int* a , int n)
16{
17 for(int i = 0; i < n ; i++)
18 cout << a[i] << ",";
19 cout << endl;
20}
21
22//分割
23int Partition(int* a, int p, int q)
24{
25 int pivot = a[p];
26 int i = p;
27
28 for(int j = p+1; j <= q; j++)
29
{
30 if(a[j] <= pivot)
31 {
32 i = i + 1;
33 swap(a[i],a[j]);
34
}
35 }
36 swap(a[i],a[p]);
37 return i;
38}
39
40//重復迭代函數
41int SelectStep(int *a, int p, int q, int i)
42{
43 if( p==q ) return a[p];
44
45 else
46 {
47 int k = Partition(a,p,q);
48
49 //i-1而不是i是因為下標是從0開始
50 //k-p而不是k，這點要特別注意??！
51 if( i-1 == k-p)
52 return a[i-1];
53 else if( i-1 < k-p)
54 return SelectStep(a,p,k-1,i);
55 else
56 return SelectStep(a,k+1,q,i-k-1);
57 }
58}
59
60//最終調用函數
61int Select(int* a, int size, int ith)
62{
63 return SelectStep(a,0,size-1,ith);
64}
65
66int main()
67{
68 const int N = 8;
69
70 int a[N] = {6,10,13,5,8,3,2,11};
71
72 print(a,N);
73
74 cout << Select(a,N,7) << endl;
75
76 system("pause");
77 return 0;
78}