找出一個數組裡面前K個最大數

前言：今天早上來實驗室，同桌問了我一個問題：找出一個數組裡面前K個最大數的高效算法。最近正好在看資料結構和算法相關内容，便以己之力幫她思考了思考。

問題：找出一個數組裡面前K個最大數。

解法：

1.第一感覺就是對數組進行降序全排序，然後傳回前K個元素，即是需要的K個最大數。

排序算法的選擇有很多，考慮數組的無序性，可以考慮選擇快速排序算法，其平均時間複雜度為O(NLogN)。具體代碼實作可以參見相關資料結構與算法書籍。

2.觀察第一種算法，問題隻需要找出一個數組裡面前K個最大數，而第一種算法對數組進行全排序，不單單找出了前K個最大數，更找出了前N(N為數組大小)

個最大數，顯然該算法存在“備援”，是以基于這樣一個原因，提出了改進的算法二。 

首先建立一個臨時數組，數組大小為K，從N中讀取K個數，降序全排序(排序算法可以自行選擇，考慮數組的無序性，可以考慮選擇快速排序算法)，然後依

次讀入其餘N - K個數進來和第K名元素比較，大于第K名元素的值則插入到合适位置，數組最後一個元素溢出，反之小于等于第K名元素的值不進行插入操作。

隻待循環完畢傳回臨時數組的K個元素，即是需要的K個最大數。同算法一其平均時間複雜度為O(KLogK + (N - K))。具體代碼實作可以自行完成。

算法時間複雜度證明：

原問題：

順序統計量選擇問題：數組A包含N個元素，找出數組A中前K個最大數

解法二：

首先建立一個臨時數組，數組大小為K，從N中讀取K個數，降序全排序(可以考慮選擇快速排序算法，快排平均複雜度O(KlogK))，

然後依次讀入其餘N - K個數進來和第K名元素比較，大于第K名元素的值則插入到合适位置，數組最後一個元素溢出，反之小于等于第K名元素的值不進行插入操作。

隻待循環完畢傳回臨時數組的K個元素，即是需要的K個最大數。

其平均時間複雜度為O(KLogK + (N - K))。

證明：

設訓示器随機變量

Xi = {A屬于前K個最大數}，i=K+1, K+2, ..., N;

由于數組A的N個元素分布随機，則E[Xi] = 1/N;

則依次處理其餘N - K個數的時間複雜度為T(N-K) = sum(Xi*logK),i=K+1, K+2, ..., N;

(注意logK是将一個數插入到排好序的K個數的時間複雜度)

對上式求期望，得

E[T(N-K)] = E[sum(Xi*logK),i=K+1, K+2, ..., N]

= sum(E[Xi] * logK),i=K+1, K+2, ..., N

= sum(1/n * logK),i=K+1, K+2, ..., N

= (N-K)logK/n < N-K;

綜合，該算法平均時間複雜度為

T(N) = O(KLogK + (N - K))。

3.上面兩種算法在N=100萬，K=50萬時速度都尤其“漫長“，現在提出一種更高效的算法，該算法原理和快速排序一緻，但隻有一個方向的遞歸，其平均時間

複雜度為O(N)。

先選取一個中值元素(該中值是否合理将影響到算法效率，其原因同快速排序)，然後将大于等于該數的元素放到其右側，小于該數的放到左側。如7 4 6 8 0 

-1，選取6作為中值元素，則結果應該為4 0 -1 6 8 7，接下來比較K值和現在的中值元素6所在索引(3)。

如果K小于索引3，則處于包括中值元素在内的右邊的元素即是前K個最大數中的前(3(索引) - K + 1)個最大數，予以儲存，同時需在索引0 ~ 2間再進行遞歸操作繼續選取第K名。

如果K大于索引3，則在4 ~ 5中遞歸選取第K - 3(索引) - 1名即可。

還有一關鍵是可以為遞歸中的數組長度選取一臨界點，小于該臨界則進行全排序，而不再進行遞歸操作。

以上算法均是本人在書本上或者網際網路上學習的算法，并非自己原創，當然部分的改動還是自我原創的。

其實當問題規模不是很大時，比如數組大小N很小，N為100數量級，可以不用太追求算法的高效性，因為對于問題規模不大時，上面三種算法的運作時間相差并不大，

完全可以考慮采用第一種或者第二種比較簡單的實作方式。