作者：dorseyCh 來源：http://www.imooc.com/article/264180
很久之前有過一次面試，被問到一個問題，能不能寫一個冒泡排序？說實話，盡管在這之前曾經寫過不少比這個更加復雜的處理邏輯，但很悲劇的是我當時真不知道什么是冒泡排序。。。只知道如果讓我排序某段混亂序列，能很快搞定就是了，最后的結果顯而易見，我被赤裸裸的鄙視了。。。（連個性能最差的冒泡排序思維都不會，要你何用= =），第二天回去，看了啥是排序，真的捶胸了半天，名字叫得那么好聽，原來是這個。。。
簡單的排序算法基本是下面這幾種，其中的話冒泡排序，選擇排序，插入排序是性能最差，實際應用基本不用但也是最簡單，能提高你算法信心的幾個小排序方式。
下面的話，我們一個個來實現，假如我們要讓[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回來對吧？當然記得把中間那家伙給放進去，別漏了?？聪孪旅妫?/p>
嗯，是不是很直觀？呵呵，但是要知道，排序，特別是排序數據非常多的時候，最考驗的就是性能，而代碼中left = [], right = []；還遞歸，這個內存的開銷是非常大的，所以我們不這樣，那怎么做呢？
上面的雖然沒重新創建數組，但是呢？通過交換，比如說大于參考點的放左邊，小于的放右邊，那我直接等待一下，一個從左邊開始掃描，一個從右邊，當左邊掃描到比參考數大的數時，結束掃描，右邊也掃描，當有一個數比參考數小時，就結束掃描，這時候把這兩個數交換一下，是不是就實現了小的在前面大的在后面，你說，可他們不一定在參考點兩邊?。繘]錯，這個時候繼續掃描，等到i和j在某個點相遇的時候，把這個參考點的值跟那個位置的值換一下，不就實現兩邊一邊大一邊小嘛。、
嗯，有了一個了，當然得有無數次，左邊那塊再繼續做這個事，右邊的也一樣，當右邊跟左邊再加上中間的數長度剛好為3或小于3的時候不就OK了？
7
堆排序
這時候還有一個性能也很不錯的排序，用到完全二叉樹的方式來的。
它又是怎么想的？臥槽（沒文化的我只會這一句= =），不就個排序，非得弄那么多亂七八糟的？嗯，怎么說呢，這是一種思想，先不扯遠一起看看具體是怎么樣的吧。
堆，有大頂堆跟小頂堆之分，這里就不扯概念了，那個官方講得很詳細嗯也很官方= =，簡單理解一下就是一個金字塔，你是幫主，你下面還有左右護法四大天王八大金剛十六羅漢，嗯就這樣一直下去，而所謂的大頂堆就是作為幫主的你是住塔頂的，小頂堆呢？則相反，你們幫最小最小的那個小弟就在那。大概是這樣哈：
這個就是所謂的大頂堆，生活中是不是太常見了？（理解為主，請忽略圖= =）
那它又是怎么做到排序的？
還記得選擇排序是怎么排序的？就是選擇一個最大數不斷的插入到最后的對吧？但是選擇最大數的那個過程是通過不斷的比較，一個個位置挪動去得到的，那能不能跳著走？跳著掃描。實際上，分成堆只是讓我們更好理解。
一起看看代碼是怎么樣實現的吧：
下面是做的一個簡單的性能測試
① 普通插入排序與快速排序的速度對比（數據量20萬）：
可以看到在20萬隨機數（0-10000）的排序中，快排所花的時間不足100個時間單位，而插入排序要超過50000個。普通的O(n²)的性能與最好情況O（nlogn）的快排是完全沒法比（數據量越龐大結果越明顯）。
② 希爾排序與快速排序對比（數據量2000萬）：
由于這兩個排序都是極不穩定的，但是從測試的幾次結果看，希爾排序的性能會略微優于快排（語言：JAVAscript）
③歸并排序與希爾排序
歸并排序相對于希爾，快排的不穩定來說，歸并排序最好跟最壞的情況均是nlogn，是穩定且快捷的排序算法。利用的正是完全二叉樹的思維模式。
④堆排序與歸并排序
也是2000萬1-10000的隨機數排序。
