/*
* 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}