在面試字節跳動的過程中，現場寫算法代碼是繞不開的一個環節。其中快速排序(Quick Sort)、快速選擇(Quick Select)是最常見的算法題之一。快速選擇是目前解決TopK問題的最優算法，如果想拿下字節跳動的offer，快速排序算法是必須要掌握的算法之一！
開篇先出到面試題，請讀者思考一下可能的解法：
給你一個無序數組，請找出其中第K大的數，時間復雜度控制在O(N)。
如果不對時間復雜度加約束的情況下，該題有很多種可能解法，例如：
- 用任意一種性能不錯的排序算法先將數組進行排序，然后從中找到位置k的數值。但即便用當前最好的排序算法，時間復雜度也是在O(n·log n)的級別，不符合題目要求。
- 用大頂堆算法，僅保留K個最大的值。這種算法的時間復雜度雖然優于前面一種，但時間復雜度也是O(n·log k)的級別，依然不滿足題目要求。
因此，為了達到題目中要求，就必須要引出今天的主角：快速選擇算法(Quick Select)。快速選擇算法是目前解決TopK問題的最優解。其核心思想和快速排序類似，因為這兩個經典算法的提出者都是同一個人——C.A.R.Hoare。
快速選擇的執行步驟是先從數組中隨機選擇一個元素作為pivot，然后遍歷數組，將<pivot的元素都放在pivot左側，≥pivot的元素都放在pivot右側。如此遍歷完以后，如果要找第k大的數，可以判斷pivot兩側元素個數。假設pivot右側元素個數≥k可推斷出，第k大的數一定在pivot右側的元素中，因此拿pivot右側部分作為新數組重新進行一輪找出第k大元素的快速選擇即可。若pivot右側元素個數<k，可知，第k大的數一定在pivot左側，因此以pivot左側所有元素作為新數組，重新進行一輪快速選擇，但是k的值就變為k-右側元素個數，因為最大的若干個元素都在pivot右側中，所以要從k中減去這些右側元素的個數。
以下是一個快速選擇的示例：
以下是基于JAVA實現的快速選擇的代碼，僅供參考：
public int findTopK(int[] nums, int k, int start, int end) {
if (k <= 0) {
throw new IllegalArgumentException("K can not less than 1!");
} else if (k > (end - start + 1)) {
throw new IllegalArgumentException("K out of range! start = " + start + ", end = " + end + ", k = " + k);
}
if (k == 1) {
int max = Integer.MIN_VALUE;
for (int i = start; i <= end; i++) {
max = Math.max(max, nums[i]);
}
return max;
}
int rand = new Random().nextInt(k);
int tmp = nums[end];
nums[end] = nums[start + rand];
nums[start + rand] = tmp;
int pivot = nums[end];
int l = start, r = start;
while (r < end) {
if (nums[r] > pivot) {
r++;
} else {
tmp = nums[r];
nums[r] = nums[l];
nums[l] = tmp;
l++;
r++;
}
}
tmp = pivot;
nums[end] = nums[l];
nums[l] = tmp;
if (start + (end - start + 1) - l >= k) {// 若右側（含l）數量≥k
return findTopK(nums, k, l, end);
} else {// 右側（含l）數量不足k
return findTopK(nums, k - (end - l + 1), start, l - 1);
}
}
快速選擇的時間復雜度是O(n)，推論依據是快速選擇每次遍歷的元素個數預期都會減半，因此全部要遍歷的元素個數是：
Sn = n + n/2 + n/4 + …… + 1
這是一個典型的等比數列求和，套用等比數列求和公式可得：
Sn = n + n/2 + n/4 + …… + 1 = (a1 - an · q) / (1 - q)= (n - 0.5) / 0.5 = 2n - 1
去除不必要的常數，僅保留數量級之后可得，快速排序的預期時間復雜度是O(n)
現如今互聯網求職競爭越發激烈，難度越發困難，如果不做好充足的復習，很可能會喪失寶貴的面試機會！關注我，定期高頻更新優質面試寶典，幫助你在職場中平步青云，斬獲理想offer！
