求第k大的数？

求第k大的数？

快排思想：

在待排序的序列中选取一个值作为一个基准，按照这个基准值得大小将这个序列划分成两个子序列，基准值会在这两个子序列的中间，一边是比基准小的，另一边就是比基准大的。这样快速排序第一次排完，我们选取的这个基准值就会出现在它该出现的位置上。这就是快速排序的单趟算法，也就是完成了一次快速排序。然后再对这两个子序列按照同样的方法进行排序，直到只剩下一个元素或者没有元素的时候就停止，这时候所有的元素都出现在了该出现的位置上。

快排之后 数组变得有序，找第k大的数，直接输出下标为k-1的数

// ConsoleApplication2.cpp : 定义控制台应用程序的入口点。
//


#include "stdafx.h"


#include <iostream>
 
using namespace std;
 
void Q(int a[], int low, int high)
{
    if(low >= high)
    {
        return;
    }
    int first = low;
    int last = high;
    int key = a[first];
 
    while(first < last)
    {
        while(first < last && a[last] <= key)
        {
            --last;
        }
 
        a[first] = a[last];
 
        while(first < last && a[first] >= key)
        {
            ++first;
        }
         
        a[last] = a[first];    


    }
    a[first] = key;
    Q(a, low, first-1);
    Q(a, first+1, high);
}
//sort ()
//int swap(int &a,int &b)
//{int =a;a=b; b=t;}
//int p(int l,int h)
//{int r=s1[l];int i=0;int j=0;for(j=0;j<h;j++){if(r>s1[j]){swap (s1[i],s1[j]);i++}swap(s1[h],s1[i]);return i;}


int _tmain(int argc, _TCHAR* argv[])
{int d,s1[1000];
cout<<"输入元素个数"<<endl;
cin>>d;
for(int i=0;i<d;i++)
{
cin>>s1[i];
}
Q(s1,0,d-1);
cout<<"输入k"<<endl;
int k;
cin>>k;


cout<<s1[k-1];
return 0;

}

先快排，再找，可以直接用sort();