技術時間到！#1——簡單的排序算法
EaseCation能夠承載海量玩家，與它實現(xiàn)的算法緊密相關。更快的算法，能讓服務器變得更加強勁，處理更多玩家的交互信息。
今天開始，我們嘗試梳理簡單的算法。我們希望讓更多玩家理解，游戲開發(fā)背后要做出哪些努力。這次的文章，將從最簡單的算法——排序算法開始。
讓沒有順序的值變得有序，就稱作排序?！坝行颉钡亩x，更科學地講是滿足“全序關系”可達到的狀態(tài)。我們撇開計算機科學的嚴格定義，先試著給出最簡單的、為數(shù)字排序的方法。
冒泡排序
有一天，史蒂夫和安娜在池塘邊玩耍。他們馬上對石頭產(chǎn)生了興趣：怎樣把石頭，從小到大地排成一行呢？
“我們來交換這些石頭吧。只要每個石頭，都比左邊的石頭大：石頭就能排成順序了?！笔返俜蛘f，“只要交換的時候，不要把小的石頭放在右邊，就可以了?！?/p>
池塘里的小魚吐著泡泡，安娜想到了最直接的方法?！拔覀儚那暗胶?，比較每一對石頭，只要比右邊的石頭更大，我們就把它換右邊去?！?/p>
“……就像小魚吐泡泡一樣，泡泡越往上浮，越大。這樣，所有大的石頭都在一側(cè)后，石頭就有順序了?！笔返俜蚋吲d地接著話：“我們不要太累，小的石頭不要在右邊，這樣就行了?！?/p>
在這里，我們把一行石頭，看成計算機處理的數(shù)字。數(shù)字的順序應當最終正確；順序不正確的一對數(shù)字，我們稱之為逆序?qū)?/strong>。只要交換數(shù)字，讓順序不正確的數(shù)字不再出現(xiàn)，排序就完成了。
如果能夠看到這里，你已經(jīng)明白了冒泡排序的思想。恭喜你！
來，我們開始編寫下面的Rust代碼：
這里，T是數(shù)據(jù)的類型。我們提供約束Ord，說明T的比較滿足全序關系。T的全序關系，意味著對于所有T的可能取值，我們都能給兩個T值分出大小關系。
我們給定的變量arr，是一個切片類型的可變借用，包含數(shù)據(jù)本身和它的長度。
迭代變量i和j，用來遍歷所有的數(shù)據(jù)對；如果它是逆序?qū)?，我們就使用切片類型的swap函數(shù)，交換這兩個數(shù)據(jù)值。
所有的步驟完成后，切片中所有的數(shù)字將是有序的——我們的排序過程就這樣完成了。在數(shù)據(jù)已經(jīng)有序的情況下，冒泡排序是相當快速的。
讓我們回顧一下：在生活中，還有哪些時候，我們會給數(shù)字排序呢？想一想，你是怎么做的？
選擇排序
有些學習勤快的同學已經(jīng)給出答案了：我會整理桌上的書本。我挑出最長的書本，放在最下面；再拿出第二長的，也放在那里。最終，我將會有一摞從大到小排序的書本。
這就是我們對選擇排序給出的理解。處理還沒有順序的數(shù)據(jù)，只需要挑出最大，或最小的一個，然后再處理剩下的數(shù)據(jù)，做到最后就可以了。
我們來給出它的Rust代碼：
我們?nèi)匀患s束T為給定全序關系的類型，給定切片參數(shù)arr。
為了實現(xiàn)選擇排序，我們從前向后迭代。在前i個變量有序的前提下，我們在剩下的變量中，取最小的一個，和無序變量的第一個交換。最終，我們就得到了有序的切片。
一般來講，選擇排序的速度比冒泡排序慢。雖然速度慢了點，但是它需要交換操作的次數(shù)比較少。在交換操作非常耗時的前提下，使用選擇排序，會比冒泡排序節(jié)省更多時間。
你可能喜歡玩撲克牌。這時候，你也許已經(jīng)領悟了另一個算法——
插入排序
當我們拿到洗亂的撲克牌，我們會不斷抽出撲克牌。當抽出一張牌，我們會將它插入另一個位置。我們要讓插入之后，它的一側(cè)，都是比它小的牌；另一側(cè)，都是比它大的牌。重復這個過程，洗亂的撲克牌就有順序了。
這種像整理撲克牌一樣，不斷插入來排序的方法，我們給它一個名字：插入排序。
來來來，寫代碼的時間到啦～這是它的Rust代碼哦～
插入排序的過程相當容易。在變量數(shù)較少的前提下，它和選擇排序需要更少的比較次數(shù)。如果數(shù)字已經(jīng)基本有序，插入排序也能擁有不錯的性能。
上面講到的三種排序算法，是排序算法中比較簡單的；但在數(shù)據(jù)規(guī)模n上升的前提下，它們都需要把數(shù)據(jù)切片遍歷兩次，它們需要的時間為n2。
我們粗略地給出時間復雜度的定義：解決一定規(guī)模的問題，需要的大致時間可以用n表示，我們用記號大O，表示它的時間復雜度。對冒泡排序、選擇排序和插入排序而言，需要的時間為n2，所以它們的時間復雜度都是O(n2)。
當然，我們更希望沖擊更低的時間復雜度——這意味著我們的排序算法，將花費最少的時間。堆排序是一種簡單的方法，為了優(yōu)化時間開銷，我們需要學習新的數(shù)據(jù)結構：堆。
堆排序
堆是一種數(shù)據(jù)結構，它可以描述一類數(shù)組或切片。
舉一個有序切片的例子。假定arr有序，我們給出arr的表示：
這里，arr已經(jīng)從大到小排序。
我們可以把堆表示成完全二叉樹。根結點的下標為0，我們把0和它對應的數(shù)據(jù)放到樹根的位置。每個結點的下標乘以2后加上1，可以得到它左孩子的下標；左孩子再下標加上1，是右孩子的下標。
給出大頂堆的定義。大頂堆必須滿足：雙親結點的數(shù)據(jù)，大于所有兩個孩子的數(shù)據(jù)。所以，根結點的數(shù)據(jù)，一定是大頂堆中所有數(shù)據(jù)里最大的一個。
切片arr是有序的，它可以表示成大頂堆。表示如下圖：
一般的切片是沒有順序的，它們不滿足堆的定義。我們需要調(diào)整數(shù)據(jù)的位置，使之滿足堆的定義；這個操作稱為建堆。
比如對數(shù)據(jù)[4, 6, 5, 8, 9]，下圖我們建堆的第一步，我們從最后一位開始。我們發(fā)現(xiàn)數(shù)字9和它的雙親結點6，不滿足雙親結點大于孩子結點，這時候需要把它們交換。
交換后我們發(fā)現(xiàn)，數(shù)字9和它的父親結點4，不滿足雙親結點大于孩子結點。我們再次交換。
但是交換之后，4和它之下的結點又不滿足堆的定義。我們對索引1、3、4，將它們看成一個沒有整理的子樹，把1看成根結點，再次執(zhí)行上面的過程，我們將得到一個子堆。最終，我們得到了一個整理好的堆，建堆過程就完成了。
建堆完成后，最大的元素就在位置0處。我們需要從小到大排序，將它和最后一個元素交換；這樣最大的元素，就在對應的位置上了。但是，這個步驟將破壞堆的性質(zhì)，交換來的數(shù)字成為新的根結點，但它將小于它的左右兒子包含的數(shù)據(jù)。我們將調(diào)整剩下的數(shù)組，維持堆的性質(zhì)。交換和維持的過程，加起來稱為出堆。
延續(xù)上面的例子。我們將9和4交換，9將成為有序的元素之一。
這個過程破壞了堆的性質(zhì)，我們重新從4開始整理這個完全二叉樹，使之重新成為堆。
重復這個過程，最終我們將得到有序的切片：[4, 5, 6, 8, 9]。排序完成了。
在這個過程中，我們建立一個堆并保持它的性質(zhì)。如果有n個元素，我們總共需要出堆n次。每次出堆，我們在完全二叉樹的每一層，需要調(diào)整一次次序，來維護堆的性質(zhì)。
來，用Rust寫出它的代碼：
代碼的思路和圖示相同。我們在adjust_heap函數(shù)里遞歸，來維持堆中子堆的性質(zhì)；遞歸的層數(shù)并不會很深。在出堆操作時，我們可變借用切片的子切片，來表示剩下需要再次回到堆性質(zhì)的元素。這些過程后，我們的代碼將迅速得到排序的結果。
我們來做簡單的計算，來看它是否滿足優(yōu)化時間復雜度的需求。由完全二叉樹的性質(zhì)得到，它的最大層數(shù)h是向上取整的log?(n)。所以在n次出堆中，我們各需要操作log?(n)次。建堆的時間將小于出堆的時間，所以排序的時間復雜度為O(nlogn）；它小于前三個排序算法的O(n2)。
這是我們得到的第一個，時間復雜度小于O(n2)的排序算法。這個算法維護一個稱為堆的數(shù)據(jù)結構，因此我們叫它堆排序。
使用堆排序替代之前的幾種排序方法，我們的算法已做出優(yōu)化，能節(jié)省大量運算時間。非常好！
心得&體會
排序算法是所有算法中最簡單的一種。它依然能有更復雜的優(yōu)化和思路；但作為算法的基礎，我們學習后，最容易理解算法的價值。算法沒有最好，只有最符合。最復雜的排序算法不過百行；但另有些改變架構的復雜情況，優(yōu)化的代碼將達到數(shù)十萬行——所以為了優(yōu)化算法花費的時間，我們?nèi)匀恍枰獙W習大量的知識，閱讀大量學術論文，體會到游戲開發(fā)是需要不停研究的領域。
本文作者：洛佳（EaseCation團隊 開發(fā)組）
喜歡的話請三連吧～
