快速排序及查找第K个大的数。

本文提供了一种基于分治法思想的，查找第K个大的数，可以使得时间复杂地低于nlogn. 因为快排的平均时间复杂度为nlogn,但是快排是全部序列的排序，

本文查找第k大的数，则不必对整个序列进行排序。请看本文：

说明本文为原创文章，转载请注明出自：丰泽园的天空-快速排序及查找第K个大的数

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 /* 如何查找第k小的数，或者第k大的数*/
 4 partition(int data[],size_t left ,size_t right)
 5 {
 6      int i = left;
 7      int j = right;
 8      int p = (left + right) / 2;
 9      int pivot = data[p];
10      while(i < j){
11          for(; i < p && data[i] <= pivot;++i);
12          if(i < p) {
13              data[p] = data[i];
14              p = i;
15          }
16          for(; j > p && data[j] >= pivot; --j);
17          if( j > p){
18              data[p] = data[j];
19              p = j;
20          }
21      }
22        data[p] = pivot;
23        return p;
24 
25 }
26 int quick_sort(int data[],size_t left, size_t right)
27 {
28     if(left < right){
29         int index = partition(data,left,right);
30         if(index - left > 1 )  
31             quick_sort(data,left, index-1);
32         if(right - index > 1)
33             quick_sort(data,index + 1, right);
34     
35     }
36 
37 }
38 int findK(int data[], size_t left, size_t right, size_t k){
39    if(left < right){
40        int mid = partition(data,left, right);
41        if(mid - left + 1 >= k)
42            findK(data,left, mid, k );
43        else 
44            findK(data, mid + 1, right, k- (mid - left +1));
45    }
46    
47 }
48 int main()
49 {
50     int data[] = {12,2,1 ,0 ,4,11,-1, 9 ,6};
51     int len = sizeof(data)/sizeof(data[0]);
52   //  quick_sort(data,0,len - 1);
53     int i =0;
54   /* 打印原始序列 */
55     for( i = 0; i < len ; ++i)
56     {
57         printf(" %d ",data[i]);
58     }
59      findK(data,0,len - 1, 5);
60     printf("x = %d
", data[5] );
61    /* 找到第k个大的数后，序列的变化为：---快排之前*/
62     for( i = 0; i < len ; ++i)
63     {
64         printf(" %d ",data[i]);
65     }
66     printf("
");
67   /* 快排之后的序列*/
68     quick_sort(data,0,len - 1);
69     for( i = 0; i < len ; ++i)
70     {
71         printf(" %d ",data[i]);
72     }
73     printf("
");
74 
75 }

说明：查找第K个大的数，用到是分治法的思想。联想到快排中，完成一次排序，左边的序列比基准值小，右边的序列比基准值大，只要确定第k个大数在哪个序列中，只要对这个子序列进行排序即可。