n个数里面找出最大的m个数字（快排思想）

分析：这个问题，我之前遇到的时候想到的解决方案是，最小堆解决方法。建立个数为m的最小堆，然后遍历n维护这个最小堆就可以了，算法的时间复杂度是n*log(m)。还是比较高效的算法的。

今天我又发现了一种解决方法，那就是STL里面的一种算法，STL里面的nth_element就是这样的一种算法。利用类似于快速排序的过程，找到前面的m个最大的数字。

不多说了，看代码吧。通过代码可以看出，和快排基本相似。

#include <iostream>
#include <cstdio>
using namespace std;

//在m个数中寻找最大的n个数
//将数组M[m]中的最大的n(n<m)个数放在数组前面
void search(int M[], int m, int n)
{
    if (n >= m) return;
    int t = M[0];
    int i = 0, j = m - 1;
    while (i < j) {
        while (i < j && M[j] < t) --j;
        if (i < j) M[i++] = M[j];

        while (i < j && M[i] >= t) ++i;
        if (i < j) M[j--] = M[i];
    }
    M[i] = t;
    if (i < n) {
        search(&M[i+1], m - i - 1, n - i - 1);
    } else if (i > n) {
        search(M, i, n);
    }
    return;
}

void test()
{
    int M[] = {8, 3, 9, 0, 4, 2, 5, 7, 1, 6};
    int m = 10, n = 6;

    printf("原始数据:");
    for(int i =  0; i < m; ++i)
        printf("%d ", M[i]);
    printf("
");

    search(M, m, n);

    printf("结果数据:");
    for(int i = 0; i < n; ++i)
        printf("%d ", M[i]);
    printf("
");
}

int main()
{
    test();
    return 0;
}