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

谁借莪１个温暖的怀抱￠ 2022-07-17 04:14 196阅读 0赞

分析：这个问题，我之前遇到的时候想到的解决方案是，最小堆解决方法。建立个数为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("\n");
    
        search(M, m, n);
    
        printf("结果数据:");
        for(int i = 0; i < n; ++i)
            printf("%d ", M[i]);
        printf("\n");
    }
    
    int main()
    {
        test();
        return 0;
    }