TopK排序

 1 //返回支点的下标
 2 int partition(int *arr, int low, int high)
 3 {
 4     //选取第一个元素为支点
 5     int pivot = arr[low];
 6     while(low < high)
 7     {
 8         //从右往左
 9         while(low < high && arr[high] >= pivot)
10             high--;
11         //该元素小于支点，移前去
12         arr[low] = arr[high];
13 
14         //从左往右
15         while(low < high && arr[low] <= pivot)
16             low++;
17         //该元素大于支点，移到后面
18         arr[high] = arr[low];
19         //将支点移至最终的位置
20         arr[low] = pivot;
21     }
22     return low;
23 }
24 
25 //递归找到前K个数
26 int selectK(int *arr, int low, int high, int k)
27 {
28     int index = 0;
29     if(low < high)
30     {
31         index = partition(arr,low,high);
32         if(k == index)
33             index = k;//返回K
34         else if(index < k)
35             index = selectK(arr,index+1,high,k-index);//还要从右边找到k-index个数
36         else if(index > k)//从左边找前K个数
37             index = selectK(arr,low,index-1,k);
38     }
39     return index;
40 }