在日常生活中，我們經(jīng)常會(huì)遇到排序問題：

• 在打撲克牌的時(shí)候，原本拿到手上的牌是亂序的，我們會(huì)按照自己喜好的順序一張一張排好手上的牌，最后看起來是順眼的。比如小智打撲克牌會(huì)將自己手上的牌排成這樣：

小智排了一下手上的牌，這次手上的牌還不錯(cuò)

• 攝影師給畢業(yè)的同學(xué)們拍照片，要求同學(xué)們站好隊(duì)形，然后要求中間高，兩邊低的方式排隊(duì)。如果攝影師發(fā)現(xiàn)某個(gè)同學(xué)的高度跟旁邊的同學(xué)不協(xié)調(diào)，這個(gè)同學(xué)必須馬上調(diào)整自己的位置，最后是一派整齊的景象：

攝影師：嗯，你們排得不錯(cuò)

• 經(jīng)常泡圖書館的泡友，會(huì)發(fā)現(xiàn)有很多志愿者會(huì)幫忙整理圖書位置。每一本書的書背上面都有一張標(biāo)簽，書架上的圖書需要按照標(biāo)簽上的編號(hào)排好順序，這樣泡友才能快速找到想要的圖書。

小智的書架，是不是還算整齊？

這些例子就是排序問題了。排序問題不僅在生活中常見，在IT屆也常見。據(jù)說，某科技公司在做一個(gè)項(xiàng)目時(shí)遭遇大量排序問題，運(yùn)算速度奇慢，項(xiàng)目經(jīng)理非常頭痛，為招收能制伏排序問題的人才，干脆總結(jié)成了一道題目（沒想到這道題日后竟成為IT面試屆的經(jīng)典）。這道題就是：

如何在一億個(gè)數(shù)當(dāng)中找到最大的10000個(gè)數(shù)？

如果讓小智手工去找這些數(shù)，用一輩子的時(shí)間可能還不夠。當(dāng)然我們要用計(jì)算機(jī)來算，我們不僅要考慮，計(jì)算機(jī)能夠如何找到這10000個(gè)最大的數(shù)，更重要的是找到這10000個(gè)數(shù)的時(shí)間越短越好。

方法一：重復(fù)尋找法

我們可以先用最直觀的方式來做這道題目，起個(gè)名字叫重復(fù)尋找法：

第1步：我們先在這一億個(gè)數(shù)當(dāng)中，尋找到最大的那個(gè)數(shù)字，把它記錄下來。

第2步：從這一億個(gè)數(shù)字中，剔除這個(gè)最大的數(shù)字。

第3步：重復(fù)執(zhí)行第1步和第2步，直至記錄下來10000個(gè)數(shù)字。記錄下來的結(jié)果即為所求。

以挑蘋果為例，重復(fù)尋找法就好比我們?cè)谔O果堆中挑蘋果的時(shí)候，先在所有蘋果里面挑出最好的一個(gè)，然后繼續(xù)在剩余蘋果里面再挑出最好的一個(gè)……如此類推。

怎么找到最好的蘋果？那必須拿著某個(gè)蘋果，對(duì)比一遍所有蘋果，如果發(fā)現(xiàn)有更好的蘋果，把好的蘋果拿在手上，把次好的蘋果放下，直至對(duì)比完所有的蘋果后，手上拿著的就是最好的蘋果。

重復(fù)尋找法，就好比在蘋果堆中不斷挑最大最好看的蘋果到自己的籃子里

為了方便討論起見，我們?cè)O(shè)?n = 1億

我們知道，求n個(gè)數(shù)最大值的比較次數(shù)為?n，求最大值的過程需要執(zhí)行?10000?次，因此，重復(fù)尋找法的總比較次數(shù)為：

10000 × n

中場(chǎng)解答：

為什么這里只關(guān)注總比較次數(shù)？實(shí)際上我們?cè)谧雠判虻臅r(shí)候，比較次數(shù)與數(shù)據(jù)規(guī)模有明顯關(guān)系，而其他的計(jì)算比如賦值、代碼解析時(shí)間這些與數(shù)據(jù)規(guī)模無關(guān)，排序的關(guān)鍵是看比較次數(shù)。

為什么求最大值的比較次數(shù)為n呢？我們可以假想這樣的情景：先拿出n個(gè)數(shù)中第一個(gè)數(shù)，作為臨時(shí)最大值。在遍歷n個(gè)數(shù)的過程中，如果發(fā)現(xiàn)有新的數(shù)字大于臨時(shí)最大值，則以該數(shù)字為臨時(shí)最大值。遍歷完成以后，臨時(shí)最大值即真正的最大值，比較的次數(shù)只需n次。

雖然這個(gè)問題有答案了，但是心里貌似有一些遺憾，不知道大家感受到了沒？

其實(shí)，遍歷10000次，這個(gè)次數(shù)有點(diǎn)多，為什么不可以遍歷1次就得到結(jié)果呢？

方法二：局部淘汰法

實(shí)際上是可以的，還有一個(gè)能夠一步到位的方法，叫做局部淘汰法：

第1步：先創(chuàng)建一個(gè)數(shù)組，保存這1億個(gè)數(shù)字中的前10000個(gè)數(shù)字，計(jì)算數(shù)組的最小數(shù)字。

第2步：遍歷剩下的數(shù)字。如果遍歷到某個(gè)數(shù)?A?大于數(shù)組的最小數(shù)字，那么則用?A?替換掉數(shù)組的最小數(shù)字。并重新計(jì)算數(shù)組的最小數(shù)字。

第3步：遍歷完成后，數(shù)組內(nèi)的數(shù)字即為所求。

以打麻將為例，一開始我們拿了n個(gè)牌，局部淘汰法類似我們?cè)诖蚵閷⑦^程中，如果摸到一個(gè)比自己手上最壞的牌要好的牌，就打出自己手上最壞的牌……如此類推，使得勝利的概率不斷增大。

局部淘汰法，可以類比打麻將的過程，不斷更換手上的牌，使得勝利的概率越來越大

這樣，遍歷1次就能得到最后的結(jié)果了。總比較次數(shù)如何呢？

最好的情況是，如果這1億個(gè)數(shù)字剛好已經(jīng)是降序排列，那么前10000個(gè)數(shù)字就是結(jié)果，只需要進(jìn)行1次最小值的計(jì)算（比較次數(shù)為?1 × 10000），9999萬次最小值的比較（次數(shù)向上近似為 n）。

最壞的情況是，如果這1億個(gè)數(shù)字剛好已經(jīng)是升序排列，那么直到最后的10000個(gè)數(shù)字才是最終結(jié)果，因此需要進(jìn)行9999萬次最小值的計(jì)算（比較次數(shù)為?n?× 10000），9999萬次最小值的比較（次數(shù)向上近似為?n?）

因此，平均的情況是，要算5000萬次最小值（比較次數(shù)為?1/2?×?n?× 10000），要算9999萬次最小值比較（次數(shù)向上近似為 n?，因此總比較次數(shù)近似為 ：

1/2?×?n?× 10000 = 5000 × n

總比較次數(shù)下降了一半，這個(gè)優(yōu)化有點(diǎn)用。

但是……大家有沒有覺得這個(gè)方法還有優(yōu)化空間？

方法三：最小堆維護(hù)法

這個(gè)問題嘛……事實(shí)上是有的。這個(gè)方法能夠大幅度降低總比較次數(shù)，稱之為最小堆維護(hù)法：

第1步：先利用前10000個(gè)數(shù)字，搭建一個(gè)元素個(gè)數(shù)為1萬的最小堆。

有模友可能會(huì)問，什么叫做最小堆呢？小智在這里解釋一下：

首先，什么是堆?

關(guān)于堆這個(gè)概念，我們生活中的理解是東西堆在一起，比如沙堆、泥堆、還有小智的一堆東西。

計(jì)時(shí)沙漏中的小沙堆

在計(jì)算機(jī)領(lǐng)域中，堆這個(gè)概念與生活中的有一點(diǎn)點(diǎn)類似，一般的堆也是上面窄下面寬的結(jié)構(gòu)。堆結(jié)構(gòu)，非常類似圓木堆放的結(jié)構(gòu)，充滿大自然的氣息。

堆結(jié)構(gòu)，可能源自圓木木堆的靈感

堆（heap）是一種基于樹（tree）的特殊的數(shù)據(jù)結(jié)構(gòu)。堆有兩種形式，分別是最大堆（max heap）和最小堆（min heap）。在堆頂?shù)墓?jié)點(diǎn)則被稱為根節(jié)點(diǎn)。

我們關(guān)心最小堆就可以了。最小堆中，如果節(jié)點(diǎn) A 是節(jié)點(diǎn) B 的父節(jié)點(diǎn)，節(jié)點(diǎn) A 中的鍵值必定小于或者等于節(jié)點(diǎn) B 中的鍵值。根節(jié)點(diǎn)是堆的最小值。

以搬磚為例，我們要建一個(gè)金字塔，比較穩(wěn)定的結(jié)構(gòu)是下面重上面輕。最下面的我們放100kg的磚，然后上面可以放輕一點(diǎn)的磚。最小堆的結(jié)構(gòu)也是類似的，位置越往上的節(jié)點(diǎn)鍵值越小。每一個(gè)節(jié)點(diǎn)都有一個(gè)鍵值，即所對(duì)應(yīng)的數(shù)字，好比每一塊磚頭都對(duì)應(yīng)一個(gè)重量，磚頭的重量可以作為磚頭的鍵值。

座結(jié)構(gòu)穩(wěn)定的小金字塔截面結(jié)構(gòu)

堆的形式有非常多，不過堆的最常見實(shí)現(xiàn)形式是二叉堆（binary heap），最小二叉堆一般也是被直接簡(jiǎn)稱為最小堆，因此我們只需要理解二叉堆即可。我們可以畫一個(gè)最小二叉堆的例子出來感受一下：

一個(gè)最小堆示例

對(duì)圖中的最小堆分析，一共有三層圓圈，稱之為節(jié)點(diǎn)，每一個(gè)上層的節(jié)點(diǎn)都連著下層的兩個(gè)節(jié)點(diǎn)，而且上層節(jié)點(diǎn)的鍵值均比下層的兩個(gè)節(jié)點(diǎn)的鍵值要小。這個(gè)就是最小堆的特征。

我們關(guān)注另外一個(gè)方面，圖中8個(gè)元素的二叉堆里面，堆的高度是3。推而廣之，對(duì)于一個(gè)有N個(gè)元素的二叉堆，其高度為?log₂?N。

這里還需要問大家一個(gè)問題：假設(shè)最小堆堆頂?shù)逆I值改變，調(diào)整的時(shí)間是多少？

這個(gè)問題也就是問堆調(diào)整時(shí)間了。一般對(duì)于這種問題，我們都要算最壞情況。假設(shè)堆頂新鍵值大于堆里所有的數(shù)，那么堆頂這個(gè)元素需要調(diào)整到堆底，每一次調(diào)整都要下降一層，因此調(diào)整的次數(shù)為堆的高度，即?log₂?N。

建堆、堆調(diào)整以及堆排序的過程展示

解釋得有點(diǎn)長，但是對(duì)于問題的理解是有幫助的哦。

我們來繼續(xù)做題吧：

第2步：遍歷剩下的數(shù)字，與最小堆的根元素鍵值進(jìn)行對(duì)比。如果遍歷到某個(gè)數(shù)確實(shí)大于根元素的鍵值，則替換根元素的鍵值，并進(jìn)行堆調(diào)整。

第3步：遍歷完成后，最小堆當(dāng)中的所有元素對(duì)應(yīng)的數(shù)值即為所求。

剛剛說明了堆調(diào)整時(shí)間，最壞情況下調(diào)整時(shí)間為?log₂?10000。同時(shí)要進(jìn)行9999萬次最小值比較（次數(shù)向上近似為?n）。因此上述步驟的比較次數(shù)最多為：

n × log₂?10000 < 14?× n

總比較次數(shù)進(jìn)一步下降了?5000 ÷ 14 >?350?倍，這個(gè)優(yōu)化確實(shí)漂亮。

這個(gè)答案小智覺得算是滿意的了。

上面這個(gè)題目屬于?Top K?類問題，這類問題的解法，很多時(shí)候都可以用堆這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行解答，往往能得到一些不錯(cuò)的結(jié)果。

總結(jié)

以上是生活随笔為你收集整理的如何轻松将上亿的数据玩弄于股掌之中？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。