快速排序(函数版)

快速排序，函数：

 1 void qsort(int a[], int L, int R)
 2 {

if(L>=R) return; //递归终止



 3     int x = a[L]; // 枢轴元素
 4     int i = L;
 5     int j = R;
 6     
 7     while(i < j) {
 8         while(i<j && a[j]>=x)
 9             j--;
10         a[i] = a[j];
11 
12         while(i<j && a[i]<=x)
13             i++;
14         a[j]=a[i];
15     }
16     a[i]=x;
17     qsort(a, L, i-1); //左半区间递归调用
18     qsort(a, i+1, R); //右半区间递归调用
19 }
20 
21 int main()
22 {
23     int a[1000];
24     for(int i=0; i<10; i++) {
25         scanf("%d", &a[i]);
26     }
27     qsort(a, 0, 9);
28     for(int j=0; j<10; j++) {
29         printf("%d ", a[j]);
30     }
31     printf("
");
32     return 0;
33 }

2. 基于快排的思路实现top k求解

int topK(int arr[], int low, int high, int k){
        int pos =0;
        partition(arr, low, high, &pos);
        int num = high - pos + 1;
        int index = -1;
        if(num == k){
                index = pos;
        }else if(num > k){
                index = topK(arr, pos + 1, high, k);
        }else{
                index =  topK(arr, low, pos -1, k - num);
        }
        return index;
}