讀完本文，可以去力扣解決如下題目：

215.數(shù)組中的第 K 個(gè)最大元素（Medium）

快速選擇算法是一個(gè)非常經(jīng)典的算法，和快速排序算法是親兄弟。

原始題目很簡(jiǎn)單，給你輸入一個(gè)無(wú)序的數(shù)組nums和一個(gè)正整數(shù)k，讓你計(jì)算nums中第k大的元素。

那你肯定說(shuō)，給nums數(shù)組排個(gè)序，然后取第k個(gè)元素，也就是nums[k-1]，不就行了嗎？

當(dāng)然可以，但是排序時(shí)間復(fù)雜度是O(NlogN)，其中N表示數(shù)組nums的長(zhǎng)度。

我們就想要第k大的元素，卻給整個(gè)數(shù)組排序，有點(diǎn)殺雞用牛刀的感覺(jué)，所以這里就有一些小技巧了，可以把時(shí)間復(fù)雜度降低到O(NlogK)甚至是O(N)，下面我們就來(lái)具體講講。

力扣第 215 題「數(shù)組中的第 K 個(gè)最大元素」就是一道類(lèi)似的題目，函數(shù)簽名如下：

intfindKthLargest(int[]nums,intk);

只不過(guò)題目要求找第k個(gè)最大的元素，和我們剛才說(shuō)的第k大的元素在語(yǔ)義上不太一樣，題目的意思相當(dāng)于是把nums數(shù)組降序排列，然后返回第k個(gè)元素。

比如輸入nums = [2,1,5,4], k = 2，算法應(yīng)該返回 4，因?yàn)?4 是nums中第 2 個(gè)最大的元素。

這種問(wèn)題有兩種解法，一種是二叉堆（優(yōu)先隊(duì)列）的解法，另一種就是標(biāo)題說(shuō)到的快速選擇算法（Quick Select），我們分別來(lái)看。

二叉堆解法

二叉堆的解法比較簡(jiǎn)單，實(shí)際寫(xiě)算法題的時(shí)候，推薦大家寫(xiě)這種解法，先直接看代碼吧：

二叉堆（優(yōu)先隊(duì)列）是比較常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，可以認(rèn)為它會(huì)自動(dòng)排序，我們前文 手把手實(shí)現(xiàn)二叉堆數(shù)據(jù)結(jié)構(gòu) 實(shí)現(xiàn)過(guò)這種結(jié)構(gòu)，我就默認(rèn)大家熟悉它的特性了。

看代碼應(yīng)該不難理解，可以把小頂堆pq理解成一個(gè)篩子，較大的元素會(huì)沉淀下去，較小的元素會(huì)浮上來(lái)；當(dāng)堆大小超過(guò)k的時(shí)候，我們就刪掉堆頂?shù)脑?，因?yàn)檫@些元素比較小，而我們想要的是前k個(gè)最大元素嘛。當(dāng)nums中的所有元素都過(guò)了一遍之后，篩子里面留下的就是最大的k個(gè)元素，而堆頂元素是堆中最小的元素，也就是「第k個(gè)最大的元素」。

二叉堆插入和刪除的時(shí)間復(fù)雜度和堆中的元素個(gè)數(shù)有關(guān)，在這里我們堆的大小不會(huì)超過(guò)k，所以插入和刪除元素的復(fù)雜度是O(logK)，再套一層 for 循環(huán)，總的時(shí)間復(fù)雜度就是O(NlogK)?？臻g復(fù)雜度很顯然就是二叉堆的大小，為O(K)。

這個(gè)解法算是比較簡(jiǎn)單的吧，代碼少也不容易出錯(cuò)，所以說(shuō)如果筆試面試中出現(xiàn)類(lèi)似的問(wèn)題，建議用這種解法。唯一注意的是，Java 的PriorityQueue默認(rèn)實(shí)現(xiàn)是小頂堆，有的語(yǔ)言的優(yōu)先隊(duì)列可能默認(rèn)是大頂堆，可能需要做一些調(diào)整。

快速選擇算法

快速選擇算法比較巧妙，時(shí)間復(fù)雜度更低，是快速排序的簡(jiǎn)化版，一定要熟悉思路。

我們先從快速排序講起。

快速排序的邏輯是，若要對(duì)nums[lo..hi]進(jìn)行排序，我們先找一個(gè)分界點(diǎn)p，通過(guò)交換元素使得nums[lo..p-1]都小于等于nums[p]，且nums[p+1..hi]都大于nums[p]，然后遞歸地去nums[lo..p-1]和nums[p+1..hi]中尋找新的分界點(diǎn)，最后整個(gè)數(shù)組就被排序了。

快速排序的代碼如下：

關(guān)鍵就在于這個(gè)分界點(diǎn)索引p的確定，我們畫(huà)個(gè)圖看下partition函數(shù)有什么功效：

索引p左側(cè)的元素都比nums[p]小，右側(cè)的元素都比nums[p]大，意味著這個(gè)元素已經(jīng)放到了正確的位置上，回顧快速排序的邏輯，遞歸調(diào)用會(huì)把nums[p]之外的元素也都放到正確的位置上，從而實(shí)現(xiàn)整個(gè)數(shù)組排序，這就是快速排序的核心邏輯。

那么這個(gè)partition函數(shù)如何實(shí)現(xiàn)的呢？看下代碼：

熟悉快速排序邏輯的讀者應(yīng)該可以理解這段代碼的含義了，這個(gè)partition函數(shù)細(xì)節(jié)較多，上述代碼參考《算法4》，是眾多寫(xiě)法中最漂亮簡(jiǎn)潔的一種，所以建議背住，這里就不展開(kāi)解釋了。

好了，對(duì)于快速排序的探討到此結(jié)束，我們回到一開(kāi)始的問(wèn)題，尋找第k大的元素，和快速排序有什么關(guān)系？

注意這段代碼：

intp=partition(nums,lo,hi);

我們剛說(shuō)了，partition函數(shù)會(huì)將nums[p]排到正確的位置，使得nums[lo..p-1] < nums[p] < nums[p+1..hi]。

那么我們可以把p和k進(jìn)行比較，如果p < k說(shuō)明第k大的元素在nums[p+1..hi]中，如果p > k說(shuō)明第k大的元素在nums[lo..p-1]中。

所以我們可以復(fù)用partition函數(shù)來(lái)實(shí)現(xiàn)這道題目，不過(guò)在這之前還是要做一下索引轉(zhuǎn)化：

題目要求的是「第k個(gè)最大元素」，這個(gè)元素其實(shí)就是nums升序排序后「索引」為len(nums) - k的這個(gè)元素。

這樣就可以寫(xiě)出解法代碼：

這個(gè)代碼框架其實(shí)非常像我們前文二分搜索框架的代碼，這也是這個(gè)算法高效的原因，但是時(shí)間復(fù)雜度為什么是O(N)呢？按理說(shuō)類(lèi)似二分搜索的邏輯，時(shí)間復(fù)雜度應(yīng)該一定會(huì)出現(xiàn)對(duì)數(shù)才對(duì)呀？

其實(shí)這個(gè)O(N)的時(shí)間復(fù)雜度是個(gè)均攤復(fù)雜度，因?yàn)槲覀兊膒artition函數(shù)中需要利用雙指針技巧遍歷nums[lo..hi]，那么總共遍歷了多少元素呢？

最好情況下，每次p都恰好是正中間(lo + hi) / 2，那么遍歷的元素總數(shù)就是：

N + N/2 + N/4 + N/8 + … + 1

這就是等比數(shù)列求和公式嘛，求個(gè)極限就等于2N，所以遍歷元素個(gè)數(shù)為2N，時(shí)間復(fù)雜度為O(N)。

但我們其實(shí)不能保證每次p都是正中間的索引的，最壞情況下p一直都是lo + 1或者一直都是hi - 1，遍歷的元素總數(shù)就是：

N + (N - 1) + (N - 2) + … + 1

這就是個(gè)等差數(shù)列求和，時(shí)間復(fù)雜度會(huì)退化到O(N^2)，為了盡可能防止極端情況發(fā)生，我們需要在算法開(kāi)始的時(shí)候?qū)ums數(shù)組來(lái)一次隨機(jī)打亂：

前文洗牌算法詳解寫(xiě)過(guò)隨機(jī)亂置算法，這里就不展開(kāi)了。當(dāng)你加上這段代碼之后，平均時(shí)間復(fù)雜度就是O(N)了，提交代碼后運(yùn)行速度大幅提升。

總結(jié)一下，快速選擇算法就是快速排序的簡(jiǎn)化版，復(fù)用了partition函數(shù)，快速定位第 k 大的元素。相當(dāng)于對(duì)數(shù)組部分排序而不需要完全排序，從而提高算法效率，將平均時(shí)間復(fù)雜度降到O(N)。

責(zé)任編輯：xj

原文標(biāo)題：快排親兄弟：快速選擇算法詳解

文章出處：【微信公眾號(hào)：算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。