之前去面試遇到了這個問題，題目：找出無序數組中第二大的數字。
定睛一看，好簡單，一次遍歷就可以找出第二大的數字，不過，這樣寫沒有什么特別之處，因為實在是太簡單了。自己仔細想想起了之前做過的題，看看有沒有什么類似的。于是，想起了之前在網上看到的一道面試題：找出無序數組中最小的k個數。 要找出最小的k個數，可以用快速選擇算法，只要在快速排序之后，樞紐剛好是第k+1個數，那么，他左邊的數，剛好就是最小的k個數。要找出無序數組中第二大的數字，可以這樣轉換：
0）假設數組中有n個元素，a1~an，而我們要求第k大的數字，就相當于求排序后的第m = n - k + 1個數字。
1）假設一次快速排序之后，如果樞紐的是第x個（1~n）。
2）如果x = m，則這個樞紐ax就是我們要求的第k大的數字，結束；如果x < m，則對a0 ~ ax-1進行一次快速排序，重復第2）步；如果x > m，則對ax+1 ~ an 進行一次快速排序，重復第2）步。
快速選擇的代碼如下：
~~~
//a[] - 要排序的數組
//b - 要排序的子區間的開始索引
//e - 要排序的子區間的結束索引
//k - 求出排序后第k個數
int quickselect(int a[], int b, int e, int k){
int i = b ;
int j = e + 1;
int x = a[i];
while(true){
while(a[++i] < x && i < j);
while(a[--j] > x);
if(i >= j)
break;
else
swap(a[i], a[j]);
}
a[b] = a[j];
a[j] = x;
if(k - 1 == j)
return a[j];
else if(k - 1 > j)
return quickselect(a, j + 1, e, k);
else
return quickselect(a, b, j - 1, k);
}
~~~
總結：快速選擇可以用于這類面試題：
1）求出無序數組中第k大的數
2）求出無序數組中最大/小的k個數
