面試：用快排實作數組中的第K大的數

1 #include <iostream>
 2 #include <cassert>
 3 using namespace std;
 4 
 5 int selectKth(int a[],int start,int end,int k){
 6     assert(start <= end && k <= end+1);
 7     int left = start;
 8     int right = end;
 9     int pivotVal = a[left];
10     while(left < right){
11         while(left < right && a[right] >= pivotVal) right--;
12         a[left] = a[right];
13         while(left < right && a[left] <= pivotVal) left++;
14         a[right] = a[left];
15     }
16     a[left] = pivotVal;
17     if(left+1 == k) return a[left];
18     else if(left+1 < k) return selectKth(a,left+1,end,k);
19     else return selectKth(a,start,left-1,k);
20 }
21 
22 int main() {
23     int a[10] = {1,3,5,6,7,8,2,4};
24 
25     std::cout << selectKth(a,0,7,2) << std::endl;
26     std::cout << selectKth(a,0,7,7) << std::endl;
27 
28     return 0;
29 }