題目描述
輸入n個整數，輸出其中最小的k個。
分析與解法
解法一
要求一個序列中最小的k個數，按照慣有的思維方式，則是先對這個序列從小到大排序，然後輸出前面的最小的k個數。
至於選取什麼的排序方法，我想你可能會第一時間想到快速排序（我們知道，快速排序平均所費時間為n*logn），然後再遍歷序列中前k個元素輸出即可。因此，總的時間複雜度：O（n * log n)+O(k)=O（n * log n）。
解法二
咱們再進一步想想，題目沒有要求最小的k個數有序，也沒要求最後n-k個數有序。既然如此，就沒有必要對所有元素進行排序。這時，咱們想到了用選擇或交換排序，即：
1、遍歷n個數，把最先遍歷到的k個數存入到大小為k的數組中，假設它們即是最小的k個數；2、對這k個數，利用選擇或交換排序找到這k個元素中的最大值kmax（找最大值需要遍歷這k個數，時間複雜度為O（k））；
3、繼續遍歷剩餘n-k個數。假設每一次遍歷到的新的元素的值為x，把x與kmax比較：如果
x < kmax ，用x替換kmax，並回到第二步重新找出k個元素的數組中最大元素kmax『；如果x >= kmax，則繼續遍歷不更新數組。每次遍歷，更新或不更新數組的所用的時間為O（k）或O（0）。故整趟下來，時間複雜度為n*O（k）=O（n*k）。
解法三
更好的辦法是維護容量為k的最大堆，原理跟解法二的方法相似：
1、用容量為k的最大堆存儲最先遍歷到的k個數，同樣假設它們即是最小的k個數；2、堆中元素是有序的，令k1<k2<...<kmax（kmax設為最大堆中的最大元素）3、遍歷剩餘n-k個數。假設每一次遍歷到的新的元素的值為x，把x與堆頂元素kmax比較：如果x < kmax，用x替換kmax，然後更新堆（用時logk）；否則不更新堆。這樣下來，總的時間複雜度:O（k+（n-k）*logk）=O（n*logk）。此方法得益於堆中進行查找和更新的時間複雜度均為：O(logk)（若使用解法二：在數組中找出最大元素，時間複雜度：O（k））。解法四
在《數據結構與算法分析--c語言描述》一書，第7章第7.7.6節中，闡述了一種在平均情況下，時間複雜度為O（N）的快速選擇算法。如下述文字：
選取S中一個元素作為樞紐元v，將集合S-{v}分割成S1和S2，就像快速排序那樣如果k <= |S1|，那麼第k個最小元素必然在S1中。在這種情況下，返回QuickSelect(S1, k)。如果k = 1 + |S1|，那麼樞紐元素就是第k個最小元素，即找到，直接返回它。否則，這第k個最小元素就在S2中，即S2中的第（k - |S1| - 1）個最小元素，我們遞歸調用並返回QuickSelect(S2, k - |S1| - 1)。此算法的平均運行時間為O(n)。
示例代碼如下：
//QuickSelect 將第k小的元素放在 a[k-1]
void QuickSelect( int a[], int k, int left, int right )
{
int i, j;
int pivot;
if( left + cutoff <= right )
{
pivot = median3( a, left, right );
//取三數中值作為樞紐元，可以很大程度上避免最壞情況
i = left; j = right - 1;
for( ； ； )
{
while( a[ ++i ] < pivot ){ }
while( a[ --j ] > pivot ){ }
if( i < j )
swap( &a[ i ], &a[ j ] );
else
break;
}
//重置樞紐元
swap( &a[ i ], &a[ right - 1 ] );
if( k <= i )
QuickSelect( a, k, left, i - 1 );
else if( k > i + 1 )
QuickSelect( a, k, i + 1, right );
}
else
InsertSort( a + left, right - left + 1 );
}
這個快速選擇SELECT算法，類似快速排序的劃分方法。N個數存儲在數組S中，再從數組中選取「中位數的中位數」作為樞紐元X，把數組劃分為Sa和Sb倆部分，Sa<=X<=Sb，如果要查找的k個元素小於Sa的元素個數，則返回Sa中較小的k個元素，否則返回Sa中所有元素+Sb中小的k-|Sa|個元素，這種解法在平均情況下能做到O(n)的複雜度。
更進一步，《算法導論》第9章第9.3節介紹了一個最壞情況下亦為O(n)時間的SELECT算法，有興趣的讀者可以參看。
舉一反三
1、谷歌面試題：輸入是兩個整數數組，他們任意兩個數的和又可以組成一個數組，求這個和中前k個數怎麼做？
分析：
「假設兩個整數數組為A和B，各有N個元素，任意兩個數的和組成的數組C有N^2個元素。
那麼可以把這些和看成N個有序數列：
A[1]+B[1] <= A[1]+B[2] <= A[1]+B[3] <=…
A[2]+B[1] <= A[2]+B[2] <= A[2]+B[3] <=…
…
A[N]+B[1] <= A[N]+B[2] <= A[N]+B[3] <=…
問題轉變成，在這N^2個有序數列裡，找到前k小的元素」
2、有兩個序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk)，A和B都按升序排列。對於1<=i,j<=k，求k個最小的（ai+bj）。要求算法儘量高效。
3、給定一個數列a1,a2,a3,...,an和m個三元組表示的查詢，對於每個查詢(i，j，k)，輸出ai，ai+1，...，aj的升序排列中第k個數。