1 /*
 2 基于区间快排的第K小算法 ,输出a[k-1]即可，O(n*logn)；每次只对后半部分递归便可把复杂度降到O(n) 
 3 主要思路是每次随机在数组中选取一个元素p，利用这个元素将数组分成两部分，比p小的元素在分好的数组左边，p和比p大的元素在数组右边，
 4 根据k值选择在数组左半或者右半部分继续递归执行查找。
 5 */
 6 #include <iostream>
 7 #include <cstring>
 8 #include <vector>
 9 #include <algorithm>
10 using namespace std;
11 
12 void swap(int *p, int *q)
13 {
14     int t;
15     t = *p;
16     *p = *q;
17     *q = t;
18 }
19 
20 int findNumberK(vector<int> &vec, int k, int from, int to)
21 {
22     int roll = vec[from], middle = 0, j = from;//roll是指标杆值 
23     for(int i = from+1 ; i<= to ; i++)
24     {
25         if(vec[i] < roll)
26         {
27             j++;//roll左边每次被换的元素 的下标 
28             swap(&vec[i], &vec[j]);
29             middle++;
30         }
31     }
32     swap(&vec[from], &vec[j]);
33     if(middle == k -1 )
34         return roll;
35     else if (middle < k - 1)
36     {
37         return findNumberK(vec, k - middle - 1, j + 1, to);
38     }
39     else
40         return findNumberK(vec, k, from, j - 1);
41 }
42 
43 int main()
44 {
45     vector<int> vec;
46     int temp, k;
47 
48     cout << "input data(以0结束):" << endl;
49     cin >> temp;
50 
51     while(temp != 0)
52     {
53         vec.push_back(temp);
54         cin >> temp;
55     }
56 
57     cout << "input K: " << endl;
58 
59     cin >> k;
60 
61     int re = findNumberK(vec , k, 0 ,vec.size() - 1);
62 
63     cout << "Test Result: "  << re << endl;
64 
65     sort(vec.begin(), vec.end(), less<int>());
66 
67     cout << "real Result: "  << vec[k-1] << endl;
68     //while(1);
69     return 0;
70 }