面試中，我輸在了簡單的排序演算法
很久之前有過一次面試，被問到一個問題，能不能寫一個氣泡排序？說實話，儘管在這之前曾經寫過不少比這個更加複雜的處理邏輯，但很悲劇的是我當時真不知道什麼是氣泡排序。。。只知道如果讓我排序某段混亂序列，能很快搞定就是了，最後的結果顯而易見，我被赤裸裸的鄙視了。。。（連個效能最差的氣泡排序思維都不會，要你何用= =），第二天回去，看了啥是排序，真的捶胸了半天，尼瑪名字叫得那麼好聽，原來是這個。。。
簡單的排序演算法基本是下面這幾種，其中的話氣泡排序，選擇排序，插入排序是效能最差，實際應用基本不用但也是最簡單，能提高你演算法信心的幾個小排序方式。
.
下面的話，我們一個個來實現，假如我們要讓[1, 2, 32, 23, 321, 45, 8, 90, 227, 99]從小到大排列。
既然要排列，我們第一反應肯定是比較，大的放後邊小的放前邊，對吧，兩兩進行比較。
1氣泡排序
先拿第1第2個數比較，誰大誰後面，接著第2個跟第3個，還是誰大誰後面，繼續第3第4，第4第5。。。這樣進行了一輪之後，你是不是可以很肯定，最後的那個數一定是最大的？接下來混亂的序列就少了一位了對吧？就繼續剩下的序列繼續上面的一輪。而你仔細想一想這個過程，12， 23， 34，...有沒有種演唱會現場一波波人浪冒出來的感覺？嗯，沒有錯，這就是冒泡，像一塊軟綿綿的地毯，裡面有一顆玻璃珠在滾動，滾著滾著這個地毯就有序了。= =嗯，這就是氣泡排序。下面看看它的程式碼是怎樣。
2選擇排序
上面的是最簡單的排序了，人的第一直覺就能產生的一種解決問題的思路。但是呢？思維肯定是不斷進步的，不可能一直停滯不前的，為什麼呢？人浪排序不是很好嗎？額不對，氣泡排序不是還不錯嘛？簡單直觀，但是你要知道，有些人的腦回路不一定如此直觀，他們解決問題的思路是這樣的：
他覺得，我每次比較後符合要求的都去交換，有些處於中間值的，不是要不斷的被交換？不是很浪費時間？我能不能選出這段序列中最大的那個數，然後放到最後邊？
答案是肯定的，怎麼做呢？既然是序列，程式碼中是陣列，那有一個下標，我先把第一個資料給存起來，這個數不斷的從第1項比到最後一項，當誰的值比他大時，他就把他的值存起來，這樣一輪過後，它拿到了最大值，這時候就把選出的這個數，仍最後。接下來那個第二大的仍這個最後的前面一項，一直到完成整個序列。這樣這種通過不斷選出剩餘項最大值的方法叫做選擇排序。
一起看看它的程式碼是怎樣的吧：
這種選擇排序，雖說沒有了交換的過程，但又多了賦值的過程，實際上並不比冒泡強哪去，也還是那樣，理論上的效能能稍微好那麼一丟丟，基本可以忽略不計。
3插入排序
跟冒泡和選擇同一時期的，還有一個插入排序，插入排序的方式更加的簡單，你想一個問題，假如你現在手上多了一個空的陣列，那你會怎樣排序？是不是先把第一個放到空陣列後，往後拿過來的數都跟這個新陣列的各個數比較，插入到某兩個數（只需注意大的在你後面，小的在你前面就OK）之間，但是呢，實際上，新建立一個數組的開銷是不算小的，沒理由一個簡單的演算法都要這樣做，所以可以這樣：
抽出第2個數，這樣就變成了前半段（你的新陣列），跟後半段（原來的大陣列），這樣不斷的把你後半段的數，插入到前半段，前半段大的就往後挪騰位置給新數插入，對吧？是不是也可以實現你想要的？一起看看這個插入排序是怎樣實現的吧。
上面這3種排序，你是不是程式碼中要有兩個for迴圈，而且是完全的遍歷，一步步走的，對吧？一個用於每一輪的比較（這時候只是進行了某一個數的比較，或者說確定了某一個數在整個陣列中它所處的位置），一個用於遍歷整個陣列，把每個成員都拿出來遛一遛。對吧，那就是n²，也就是時間複雜度O(n²)（個人理解，不一定非常準確，但個人認為還是比較好理解的，不至於說得很複雜）
既然有了前人的摸索，後人站 們這些的思維又是怎樣的呢？
4希爾排序
比如說我們在說到無論是冒泡還是插入排序，有沒有注意到“一個個的往後挪”這樣的字眼？為什麼要一個個的挪呢？能不能一大段一大段的挪？打個比方，如果排序一個1~100的陣列（原序列是100,99,98...1），這個時候100是在第1位，光排完100這個數你就得挪99次，得呼叫上面的swap方法99次，但比如說把這個一個個挪切換成一半一半的挪，比如第一個數100跟51比較後交換然後99跟52比較，是不是就非常大的邁了一大步？這些邁完後，再把間隔變成25，再來邁，雖說可能邁偏對吧？沒事最後做一個步伐為1的修正就好了。而這，就是鼎鼎有名的 希爾排序 。
看一下希爾排序是怎麼實現的哈：
5請輸入標題
看了以前上面一個個的挪實在太費勁了，我要比較，我不挪，我直接就拿出來，分成小組，每個小組自己先弄成有序的，再彙總，這樣這種分而治之思想的實際上就是歸併排序。它的核心排序點在哪呢？你分治就分治嘛，怎麼分？又怎麼治？就是我為神馬用這個排序，這個資料通過這個方法過一下就變有序了？核心就在於小組——這個小組的成員最多隻有2個，比如說陣列的長度是8，就分成了4個2，7就分成3個2跟1個1，多個數我們一眼排不出序來，兩個總可以吧？沒錯，這就是分。那怎麼治呢？我們看下下面比如說我現在A，B兩個小組已經完成了他們內部的排序（他們的長度都是4）
A B
1568 2479
手工畫，別嫌棄 = =
那一起看看它是怎麼實現的吧：
6快速排序
這個時候呢，也誕生了另一個思想，個人看來也是一種分類，它是怎樣的呢？有點類似於體育課的時候高個子站後面矮個子站前面，教練沒辦法一開始就一眼看出誰高誰矮對吧？那麼多人，肯定是隨便逮一個，來以他為基準，排序！！！一聲令下，小個的站這傢伙的前邊，大個的站後邊，對吧？而這就是快速排序的核心思想。有點像二分法，不過這個二分法有點不同，它不是按長度，它是按類，你高就佔那邊，矮就站這邊，把整體分成兩部分，那矮的那塊還能不能再分，那是當然，矮的那塊再隨便找一個，再分，這樣就完成了一個排序的內部過程。（左邊小，右邊大，那當長度為3的時候不就實現有序了嗎？嗯，這就是快排的核心思想）
具體的程式碼怎麼實現呢？
這樣很直觀的我們就想到，嘿我弄兩個陣列，裝高個子跟矮個子，然後再concat回來對吧？當然記得把中間那傢伙給放進去，別漏了。看下下面：
嗯，是不是很直觀？呵呵，但是要知道，排序，特別是排序資料非常多的時候，最考驗的就是效能，而程式碼中left = [], right = []；還遞迴，這個記憶體的開銷是非常大的，所以我們不這樣，那怎麼做呢？
上面的雖然沒重新建立陣列，但是呢？通過交換，比如說大於參考點的放左邊，小於的放右邊，那我直接等待一下，一個從左邊開始掃描，一個從右邊，當左邊掃描到比參考數大的數時，結束掃描，右邊也掃描，當有一個數比參考數小時，就結束掃描，這時候把這兩個數交換一下，是不是就實現了小的在前面大的在後面，你說，可他們不一定在參考點兩邊啊？沒錯，這個時候繼續掃描，等到i和j在某個點相遇的時候，把這個參考點的值跟那個位置的值換一下，不就實現兩邊一邊大一邊小嘛。、
嗯，有了一個了，當然得有無數次，左邊那塊再繼續做這個事，右邊的也一樣，當右邊跟左邊再加上中間的數長度剛好為3或小於3的時候不就OK了？
7堆排序
這時候還有一個性能也很不錯的排序，用到完全二叉樹的方式來的。
它又是怎麼想的？臥槽（沒文化的我只會這一句= =），不就個排序，非得弄那麼多亂七八糟的？嗯，怎麼說呢，這是一種思想，先不扯遠一起看看具體是怎麼樣的吧。
堆，有大頂堆跟小頂堆之分，這裡就不扯概念了，那個官方講得很詳細嗯也很官方= =，簡單理解一下就是一個金字塔，你是幫主，你下面還有左右護法四大天王八大金剛十六羅漢，嗯就這樣一直下去，而所謂的大頂堆就是作為幫主的你是住塔頂的，小頂堆呢？則相反，你們幫最小最小的那個小弟就在那。大概是這樣哈：
這個就是所謂的大頂堆，生活中是不是太常見了？（理解為主，請忽略圖= =）
那它又是怎麼做到排序的？
還記得選擇排序是怎麼排序的？就是選擇一個最大數不斷的插入到最後的對吧？但是選擇最大數的那個過程是通過不斷的比較，一個個位置挪動去得到的，那能不能跳著走？跳著掃描。實際上，分成堆只是讓我們更好理解。
一起看看程式碼是怎麼樣實現的吧：
下面是做的一個簡單的效能測試
① 普通插入排序與快速排序的速度對比（資料量20萬）：
可以看到在20萬隨機數（0-10000）的排序中，快排所花的時間不足100個時間單位，而插入排序要超過50000個。普通的O(n²)的效能與最好情況O（nlogn）的快排是完全沒法比（資料量越龐大結果越明顯）。
② 希爾排序與快速排序對比（資料量2000萬）：
由於這兩個排序都是極不穩定的，但是從測試的幾次結果看，希爾排序的效能會略微優於快排（語言：javascript）
③歸併排序與希爾排序
歸併排序相對於希爾，快排的不穩定來說，歸併排序最好跟最壞的情況均是nlogn，是穩定且快捷的排序演算法。利用的正是完全二叉樹的思維模式。
④堆排序與歸併排序
也是2000萬1-10000的隨機數排序。
總結
人類的思維方式是不斷進化的，一開始我們遇到問題時的解決辦法就是類似於氣泡排序，選擇排序，插入排序一樣，簡單直觀易理解上手但效率較低，但隨著時間的推移，不斷的找到更好的辦法來替代，就比如說插入排序，一開始的插入是靠著大的數一個個往後挪挪出一個位置來的，那既然可以一個位置一個位置的挪，為什麼不可以一大段一大段位置的挪呢？這樣效率不是更高？你說沒一個個位置的挪可能挪偏了，比如可能挪偏大一點，沒關係啊，後面繼續進行一次挪動就好了。這個就是希爾排序的思想。而對於選擇排序，同樣的，我要選出一個最大數，通過傳統的一個個位置掃描是最簡單直觀，但太慢了，我可不可以直接堆成堆來，不斷的比較二分的數與該二分數位置再二分的數，這樣跳著走完整個迴圈，是不是就可以快上好多？再看看快速排序，他的思想就有些不同，他的核心思想是一個序列，一定是可以分成大於某個數的一堆跟小於某個數的一堆，當這個序列只有3個數時，實際上這個序列就已經有序了。再看看歸併（或者說完全二叉樹的思想），分治，我無論多長的序列，最後，我一定是可以分成一個個長度為2的小組（或者剩餘最後一個），我只要保證分出來的這些小組都被處理成有序，最終合併就好了。
原文釋出時間為： 2018-11-26
本文作者： 程式員共成長
本文來自雲棲社群合作伙伴“ ofollow,noindex">程式設計師共成長 ”，瞭解相關資訊可以關注“ 程式設計師共成長 ”。