#include 
      
       using namespace std;int a[100], n;int part(int l, int r){    if(l > r) return -1;    int i=l,j=r;    int tmp=a[l];    while(i
       
        =tmp && i
        
         >  n;    for(int i=0;i
         
          >a[i];    int k; cin>>k;    int result = check(0,n-1,k);    cout << result;    return 0;}
         
        
       
      

  

只需找到第k大的数，不必把所有的数排好序。我们借助快排中partition过程，一般情况下，在把所有数都排好序前，就可以找到第k大的数。我们依据的逻辑是，经过一次partition后，数组被pivot分成左右两部分：S左、S右。当S左的元素个数|S左|等于k-1时，pivot即是所找的数；当|S左|小于k-1，所找的数位于S右中；当|S左|>k-1，所找的数位于S左中。显然，后两种情况都会使搜索空间缩小。

算法的时间复杂度为：O(N)，计算公式，假设我们的数据足够的随机，每次划分都在数据序列的中间位置，根据条件1，那么第一次划分我们需要遍历约n个数，第二次需要遍历约n/2个数，...，这样递归下去，最后：

 

 

快排

#include
     
      using namespace std;int a[100], n;void quick_sort(int l, int r){    if(l > r) return;    int i=l, j=r;    int tmp=a[l];    while(i
      
       =tmp && i
       
        > n;    for(int i = 0; i
        
         >a[i];    quick_sort(0,n-1);    for(int i=0; i