方法一：基于快排
1 /* 2 基于区间快排的第K小算法 ,输出a[k-1]即可，O(n*logn)；每次只对后半部分递归便可把复杂度降到O(n) 3 主要思路是每次随机在数组中选取一个元素p，利用这个元素将数组分成两部分，比p小的元素在分好的数组左边，p和比p大的元素在数组右边， 4 根据k值选择在数组左半或者右半部分继续递归执行查找。 5 */ 6 #include7 #include 8 #include 9 #include 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 &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 else40 return findNumberK(vec, k, from, j - 1);41 }42 43 int main()44 {45 vector 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 ());66 67 cout << "real Result: " << vec[k-1] << endl;68 //while(1);69 return 0;70 }