经典算法学习——求数组里面第N大的数

这是一道面试的算法题，当然可以用很多排序算法来实现，这些都是比价常规的。但是这道题要求不能排序，并且时间复杂度不能超过O(n^2).这里我们借用快速排序的衍生算法来实现。关于快速排序的实现，可以参考《经典算法学习——快速排序》这篇博客。示例代码上传至：https://github.com/chenyufeng1991/Front-N。

每一次的快排，都需要找一个基准值，然后从数组的两边交替开始和基准值比较，右边比基准值小的数移到左边，左边比基准值大的数移到右边，移到最后，只剩下一个位置了a[i]，然后把基准值填入到a[i]中。此时，在基准值右边的数都比支点大。如果此时基准值的下标为i, 那么这个基准值就是第(endIndex-i+1)大的数了。endIndex是最后一个数的下标。

我们的目标是要找第N大的数，如果endIndex-i+1 = n，表示这个数我们找到了，具体说明如下：

记th = endIndex - i + 1 （表示当前下标为i的数字排名第th位）。find(a,startIndex,endIndex,n)

（1）th = n,返回基准值；

（2）th > n,说明第n大的数在基准值右边，所以在右边继续找:find(a,i+1,endIndex,n);

（3）th < n,说明第n大的数在基准值左边，在左边找第(n-th)大的数即可；find(a,startIndex,i-1,n-th);

 

具体代码实现如下：

 

//
//  main.c
//  FrontN
//
//  Created by chenyufeng on 16/1/28.
//  Copyright © 2016年 chenyufengweb. All rights reserved.
//

#include 

int choose_nth(int a[],int startIndex, int endIndex, int n);
int main(int argc, const char * argv[]) {

    int a[] = {150,111,1000,99,300,10,189};

    int ans = choose_nth(a, 0, 6, 1);
    printf("第1大的数是:%d\n", ans);

    return 0;
}

int choose_nth(int a[], int startIndex, int endIndex, int n)
{
    int midOne = a[startIndex];//把第一个值作为支点
    int i = startIndex, j = endIndex;
    if(i == j) //递归出口之一
        return a[i];

    if(i < j){
        while(i < j){

            while (i < j && a[j] >= midOne) {
                j--;
            }
            if (i < j) {
                a[i++] = a[j];
            }

            while (i < j && a[i] < midOne) {
                i++;
            }
            if (i < j) {
                a[j--] = a[i];
            }
        }
        a[i] = midOne;//支点归位
        //此时a[i]这个数必定处于它真正的位置上，左边的都比他小，右边的都比他大；
        int th = endIndex - i + 1;//计算下标为i的数第几大，都使用下标进行计算；

        if(th == n){//正好找到
            return a[i];
        }
        else{
            if(th > n)//在支点右边找
                return choose_nth(a, i + 1, endIndex, n);
            else//在支点左边找第(n-th)大,因为右边th个数都比支点大
                return choose_nth(a, startIndex, i - 1, n - th);
        }
    }
    return 0;
}

通过查看代码知道，其中的主体部分就是快速排序。