從一堆數(shù)據(jù)中挑選n個最大的數(shù)，這個問題是網(wǎng)上流傳的比較廣的幾個問題之一。具體來說，它的意思就是：假設我們有100個數(shù)據(jù)，我們需要挑選出最大的n個數(shù)據(jù)(n < 100)，那么有沒有辦法實現(xiàn)這樣一個目標呢？在這里，我想從排序的角度看看有沒有什么辦法可以實現(xiàn)這樣一個目標。

在前面的博客當中，我們實現(xiàn)的排序算法有下面幾種：

（1） [冒泡排序][1]、[插入排序][1]、[希爾排序][1]

（2） [快速排序][2]

（3） [合并排序][3]

（4） [堆排序][4]

（5）[ 選擇排序][5]

（6） [基數(shù)排序][6]

那么是不是這8種算法都適合今天的題目呢？我簡單的對它們進行了分析和歸類：

a）不到最后無法求出最大數(shù)據(jù)的算法，（[插入算法][1]，[合并算法][3]，[基數(shù)排序][6]）

這些算法的特點就是可以保證局部的數(shù)據(jù)基本有序，但是無法保證全局的數(shù)據(jù)有序。在全部數(shù)據(jù)得到正確地排序之前，沒有人知道最大的數(shù)據(jù)是什么。所以針對這個題目而言，要想知道最大的n個數(shù)，那就等于要對所有的數(shù)據(jù)全部排序一遍。

b）每次求出一個最大的數(shù)據(jù)，依次類推，直到所有的數(shù)據(jù)都已經(jīng)排序。（[冒泡排序][1]、[希爾排序][1]、[選擇排序][5]、[堆排序][4]）

這些算法的特點就是，排序的時候，所有的數(shù)據(jù)都是按照從大到小排列出來的。按照冒泡排序來說，首先我們選出最大的數(shù)據(jù)，然后是第二大的數(shù)據(jù)，依次類推，直到第n大的數(shù)據(jù)找到為止。堆排序也是這樣，我們在構建堆之后，也是每次從堆頂獲得一個數(shù)據(jù)，不斷調整堆，再接著獲得第二大、第三大......第n大的數(shù)據(jù)的。我們以冒泡排序為例，看看這一次的算法應該怎么寫？

void find_n_max_number(int array[], int length, int number)
{
    int inner ;
    int outer;
    int median;

    if(NULL == array || 0 == length)
        return;

    if(number > length)
        return;

    for(outer = length -1; outer > (length - 1 - number); outer --){
        for(inner = 0; inner < outer; inner ++){
            if(array[inner] > array[inner +1]){
                median = array[inner];
                array[inner]  = array[inner + 1];
                array[inner + 1]= median;
            }
        }
    }
}

c）迭代搜索，首先對數(shù)據(jù)進行分類，小于于數(shù)組第一個數(shù)據(jù)的排在左邊，大于的排在右邊。如果右邊的數(shù)據(jù)小于n，為m，那么在左邊數(shù)組繼續(xù)尋找剩下的（n-m）個數(shù)據(jù)；如果右邊的數(shù)據(jù)大于n，那么在右邊的數(shù)據(jù)繼續(xù)尋找。（[快速排序][2]）
不知道上面的解釋說明白了沒，沒有清楚的同學可以看一看下面這個代碼。

int partion(int array[], int start, int end, int swap[])
{
    int loop;
    int left = 0;
    int right = end - start;
    int value = array[start];

    for(loop = start +1; loop <= end; loop++){
        if(array[loop] < value)
            swap[left ++] = array[loop];
        else
            swap[right --] = array[loop];
    }
    swap[left] = value;
    memmove(&array[start], swap, sizeof(int) * (end - start +1));
    return left + start;
}

void _quick_sort(int array[], int start, int end, int swap[], int number)
{
    int middle;

    if(start < end){
        middle = partion(array, start, end, swap);

        if((number - 1) > (end - middle))
            _quick_sort(array, start, middle -1, swap, number - (end - middle + 1));
        else
            _quick_sort(array, middle + 1, end, swap, number);
    }
}

void find_n_max_number(int array[], int length, int number)
{
    int* swap ;
    if(NULL == array || 0 == length)
        return;

    swap = (int*)malloc(sizeof(int) * length);
    _quick_sort(array, 0, length-1, swap, number);
    free(swap);
}

總結：

至于這些算法的結果怎么樣，各位朋友們可以自己利用自己的電腦好好測試一下。