排序

排序的目標是將一組數據 (即一個序列) 重新排列，排列後的數據符合從大到小 (或者從小到大) 的次序。這是古老但依然富有挑戰的問題。從無序到有序，有效的減小了系統的熵值，增加了系統的有序度。對於一個未知系統來說，有序是非常有用的先驗知識。因此，排序算法很多時候構成了其他快速算法的基礎，比如二分法就是基於有序序列的查找算法。直到今天，排序算法依然是計算機科學積極探索的一個方向。

完整代碼，以及更多學習資料，私信“代碼“獲取

我在這裡列出一些最常見的排序方法，(雖說百度有一大堆，在這裡就代為總結吧)並使用C語言實現它們。一組數據存儲為一個數組a，數組有n個元素。a[i]為數組中的一個元素，i為元素在數組中的位置 (index)。根據C的規定，數組下標從0開始。假設數組從左向右排列，下標為0的元素位於數組的最左邊。序列將最終排列成從小到大的順序。下面函數中的參數ac是數組中元素的數目，也就是n。

完整代碼，以及更多學習資料，私信“代碼“獲取

冒泡排序 (Bubble Sort)

冒泡排序相當暴力的實現了這一目標：不斷掃描相鄰元素，看它們是否違章。一旦違章，立即糾正。在冒泡排序時，計算機從右向左遍歷數組，比較相鄰的兩個元素。如果兩個元素的順序是錯的，那麼sorry，請兩位互換。如果兩個元素的順序是正確的，則不做交換。

完整代碼，以及更多學習資料，私信“代碼“獲取

插入排序 (Insertion Sort)

假設在新生報到的時候，我們將新生按照身高排好隊(也就是排序)。如果這時有一名學生加入，我們將該名學生加入到隊尾。如果這名學生比前面的學生低，那麼就讓該學生和前面的學生交換位置。這名學生最終會換到應在的位置。這就是插入排序的基本原理。

選擇排序 (Selection Sort)

選擇排序是先找到起始數組中最小的元素，將它交換到i=0；然後尋找剩下元素中最小的元素，將它交換到i=1的位置…… 直到找到第二大的元素，將它交換到n-2的位置。這時，整個數組的排序完成。

希爾排序（Shell Sort）

希爾排序是以更大的間隔來比較和交換元素，這樣，大的元素在交換的時候，可以向右移動不止一個位置，從而更快的移動烏龜元素。比如，可以將數組分為4個子數組（i=4k, i=4k+1, i=4k+2, i=4k+3），對每個子數組進行冒泡排序。比如子數組i=0，4，8，12...。此時，每次交換的間隔為4。完成對四個子數組的排序後，數組的順序並不一定能排列好。希爾排序會不斷減小間隔，重新形成子數組，並對子數組冒泡排序…… 當間隔減小為1時，就相當於對整個數組進行了一次冒泡排序。隨後，數組的順序就排列好了。希爾排序不止可以配合冒泡排序，還可以配合其他的排序方法完成。

Shell Sorting依賴於間隔(step)的選取。一個常見的選擇是將本次間隔設置為上次間隔的1/1.3。

歸併排序 (Merge Sort)

如果我們要將一副撲克按照數字大小排序。此前已經有兩個人分別將其中的一半排好順序。那麼我們可以將這兩堆撲克向上放好，假設小的牌在上面。此時，我們將看到牌堆中最上的兩張牌。

我們取兩張牌中小的那張取出放在手中。兩個牌堆中又是兩張牌暴露在最上面，繼續取小的那張放在手中…… 直到所有的牌都放入手中，那麼整副牌就排好順序了。這就是歸併排序。

完整代碼，以及更多學習資料，私信“代碼“獲取

快速排序 (Quick Sort)

我們依然考慮按照身高給學生排序。在快速排序中，我們隨便挑出一個學生，以該學生的身高為參考(pivot)。然後讓比該學生低的站在該學生的右邊，剩下的站在該學生的左邊。很明顯，所有的學生被分成了兩組。該學生右邊的學生的身高都大於該學生左邊的學生的身高。我們繼續，在低身高學生組隨便挑出一個學生，將低身高組的學生分為兩組(很低和不那麼低)。同樣，將高學生組也分為兩組(不那麼高和很高)。如此繼續細分，直到分組中只有一個學生。當所有的分組中都只有一個學生時，則排序完成。

理想的pivot是採用分組元素中的中位數。然而尋找中位數的算法需要另行實現。也可以隨機選取元素作為pivot，隨機選取也需要另行實現。為了簡便，我每次都採用中間位置的元素作為pivot。

堆排序 (Heap Sort)

完整代碼，以及更多學習資料，私信“代碼“獲取

堆(heap)是常見的數據結構。它是一個有優先級的隊列。最常見的堆的實現是一個有限定操作的Complete Binary Tree。這個Complete Binary Tree保持堆的特性，也就是父節點(parent)大於子節點(children)。因此，堆的根節點是所有堆元素中最小的。堆定義有插入節點和刪除根節點操作，這兩個操作都保持堆的特性。我們可以將無序數組構成一個堆，然後不斷取出根節點，最終構成一個有序數組。(大頂堆，代碼後續文章會更新，這裡就不列舉出來了)。