问题描述：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k大的元素，（这里给定的线性集是无序的）。

　　其实这个问题很简单，直接对线性序列集qsort，再找出第k个即可。但是这样的时间复杂度就是qsort的时间复杂度O(nlogn)。有没有更快的方法呢？看到网上有一种解法是采取了快排的思路，但是稍微坐了些改动，然后时间复杂度能够接近O(n)。因为最近刚刚写了快排的实现，所以在这我就再把这个实现一次吧。

　　解题思路：与快排不同的是，这里只对划分出来的其中一组进行递归处理。任意选定一个pivotIndex，pivotValue = arr[pivotIndex]。经过一次划分后，pivotValue存储在storeIndex的位置，storeIndex把数组划分为两部分。比pivoteValue大的在前面，比pivotValue小的存储在后面（此时前后两部分是没有排好序的）。那么storeIndex位置的pivotValue就肯定是第storeIndex大的数。然后用K于storeIndex比较，如果K<storeIndex,那么说明第K大一定在右边，那么再对右边进行划分即可。如果K>storeIndex,那么说明第K大一定在左边，那么再对左边进行划分。然后递归，最后就可以得到第K大。

#include 
     
      void swap(int *a, int *b){    int tmp;    tmp = *a;    *a = *b;    *b = tmp;}int partition(int arr[], int left, int right, int pivotIndex){    int storeIndex = left;    int pivotValue = arr[pivotIndex];    int i;    swap(&arr[pivotIndex],&arr[right]);        for (i = left; i < right; i ++)    {        if (arr[i] > pivotValue)        {            swap(&arr[i],&arr[storeIndex]);            storeIndex++;        }    }    swap(&arr[storeIndex],&arr[right]);    return storeIndex;}int findKMax(int arr[], int left, int right, int k){    int nRet;    int pivotIndex = left + 1;    nRet = partition(arr,left,right,pivotIndex);    if (nRet < k)    {        return findKMax(arr,nRet+1,right,k);    }    else if (nRet > k)    {        return findKMax(arr,left,nRet-1,k);    }            return nRet;}int main(){    int i,k,nRet;    int arr[] = {
   8,3,4,1,9,7,6,10};    scanf("%d",&k);    nRet = findKMax(arr,0,7,k-1);        printf("The Kth Max Number locate in %d is :%d\n",nRet,arr[nRet]);    for (i = 0; i < 8; i++)    {        printf("%3d",arr[i]);    }    return 0;}  2013/6/17  19:55
     

 

　　列出了很多种寻找第K大数的算法。

第二次实现该算法：

#include 
     
      void swap(int arr[], int i, int j){    int tmp;    tmp = arr[i];    arr[i] = arr[j];    arr[j] = tmp;}int partition(int arr[], int left, int right){    int value = arr[left];    int p_insert,p_cmp;    swap(arr,left,right);    p_insert = p_cmp = left;    while (p_cmp < right)    {        if (arr[p_cmp] < value)        {            swap(arr,p_insert,p_cmp);            p_insert++;        }        p_cmp++;    }    swap(arr,p_insert,right);    return p_insert;}void max_k(int arr[], int left, int right,int k){    int ret = partition(arr,left,right);    if (ret == k) return;    else if (ret < k)        ret = partition(arr,ret+1,right);    else        ret = partition(arr,left,ret);     }int main(){    int arr[] = {
   9,10,7,8,3,12,15,76,6};    int i,k = 5;    max_k(arr,0,8,k);    for (i = 0; i < k; i++)    {        printf("%d ",arr[i]);    }    printf("\n");    return 0;}2013/10/21  22:42