作者：dorseyCh 來源：http://www.imooc.com/article/264180
很久之前有過一次面試，被問到一個(gè)問題，能不能寫一個(gè)冒泡排序？說實(shí)話，盡管在這之前曾經(jīng)寫過不少比這個(gè)更加復(fù)雜的處理邏輯，但很悲劇的是我當(dāng)時(shí)真不知道什么是冒泡排序。。。只知道如果讓我排序某段混亂序列，能很快搞定就是了，最后的結(jié)果顯而易見，我被赤裸裸的鄙視了。。。（連個(gè)性能最差的冒泡排序思維都不會(huì)，要你何用= =），第二天回去，看了啥是排序，真的捶胸了半天，名字叫得那么好聽，原來是這個(gè)。。。
簡(jiǎn)單的排序算法基本是下面這幾種，其中的話冒泡排序，選擇排序，插入排序是性能最差，實(shí)際應(yīng)用基本不用但也是最簡(jiǎn)單，能提高你算法信心的幾個(gè)小排序方式。
下面的話，我們一個(gè)個(gè)來實(shí)現(xiàn)，假如我們要讓[1, 2, 32, 23, 321, 45, 8, 90, 227, 99]從小到大排列。
既然要排列，我們第一反應(yīng)肯定是比較，大的放后邊小的放前邊，對(duì)吧，兩兩進(jìn)行比較。
1
冒泡排序
先拿第1第2個(gè)數(shù)比較，誰大誰后面，接著第2個(gè)跟第3個(gè)，還是誰大誰后面，繼續(xù)第3第4，第4第5。。。這樣進(jìn)行了一輪之后，你是不是可以很肯定，最后的那個(gè)數(shù)一定是最大的？接下來混亂的序列就少了一位了對(duì)吧？就繼續(xù)剩下的序列繼續(xù)上面的一輪。而你仔細(xì)想一想這個(gè)過程，12， 23， 34，...有沒有種演唱會(huì)現(xiàn)場(chǎng)一波波人浪冒出來的感覺？嗯，沒有錯(cuò)，這就是冒泡，像一塊軟綿綿的地毯，里面有一顆玻璃珠在滾動(dòng)，滾著滾著這個(gè)地毯就有序了。= =嗯，這就是冒泡排序。下面看看它的代碼是怎樣。
2
選擇排序
上面的是最簡(jiǎn)單的排序了，人的第一直覺就能產(chǎn)生的一種解決問題的思路。但是呢？思維肯定是不斷進(jìn)步的，不可能一直停滯不前的，為什么呢？人浪排序不是很好嗎？額不對(duì)，冒泡排序不是還不錯(cuò)嘛？簡(jiǎn)單直觀，但是你要知道，有些人的腦回路不一定如此直觀，他們解決問題的思路是這樣的：
他覺得，我每次比較后符合要求的都去交換，有些處于中間值的，不是要不斷的被交換？不是很浪費(fèi)時(shí)間？我能不能選出這段序列中最大的那個(gè)數(shù)，然后放到最后邊？
答案是肯定的，怎么做呢？既然是序列，代碼中是數(shù)組，那有一個(gè)下標(biāo)，我先把第一個(gè)數(shù)據(jù)給存起來，這個(gè)數(shù)不斷的從第1項(xiàng)比到最后一項(xiàng)，當(dāng)誰的值比他大時(shí)，他就把他的值存起來，這樣一輪過后，它拿到了最大值，這時(shí)候就把選出的這個(gè)數(shù)，仍最后。接下來那個(gè)第二大的仍這個(gè)最后的前面一項(xiàng)，一直到完成整個(gè)序列。這樣這種通過不斷選出剩余項(xiàng)最大值的方法叫做選擇排序。
一起看看它的代碼是怎樣的吧：
這種選擇排序，雖說沒有了交換的過程，但又多了賦值的過程，實(shí)際上并不比冒泡強(qiáng)哪去，也還是那樣，理論上的性能能稍微好那么一丟丟，基本可以忽略不計(jì)。
3
插入排序
跟冒泡和選擇同一時(shí)期的，還有一個(gè)插入排序，插入排序的方式更加的簡(jiǎn)單，你想一個(gè)問題，假如你現(xiàn)在手上多了一個(gè)空的數(shù)組，那你會(huì)怎樣排序？是不是先把第一個(gè)放到空數(shù)組后，往后拿過來的數(shù)都跟這個(gè)新數(shù)組的各個(gè)數(shù)比較，插入到某兩個(gè)數(shù)（只需注意大的在你后面，小的在你前面就OK）之間，但是呢，實(shí)際上，新創(chuàng)建一個(gè)數(shù)組的開銷是不算小的，沒理由一個(gè)簡(jiǎn)單的算法都要這樣做，所以可以這樣：
抽出第2個(gè)數(shù)，這樣就變成了前半段（你的新數(shù)組），跟后半段（原來的大數(shù)組），這樣不斷的把你后半段的數(shù)，插入到前半段，前半段大的就往后挪騰位置給新數(shù)插入，對(duì)吧？是不是也可以實(shí)現(xiàn)你想要的？一起看看這個(gè)插入排序是怎樣實(shí)現(xiàn)的吧。
上面這3種排序，你是不是代碼中要有兩個(gè)for循環(huán)，而且是完全的遍歷，一步步走的，對(duì)吧？一個(gè)用于每一輪的比較（這時(shí)候只是進(jìn)行了某一個(gè)數(shù)的比較，或者說確定了某一個(gè)數(shù)在整個(gè)數(shù)組中它所處的位置），一個(gè)用于遍歷整個(gè)數(shù)組，把每個(gè)成員都拿出來遛一遛。對(duì)吧，那就是n²，也就是時(shí)間復(fù)雜度O(n²)（個(gè)人理解，不一定非常準(zhǔn)確，但個(gè)人認(rèn)為還是比較好理解的，不至于說得很復(fù)雜）
既然有了前人的摸索，后人站 們這些的思維又是怎樣的呢？
4
希爾排序
比如說我們?cè)谡f到無論是冒泡還是插入排序，有沒有注意到“一個(gè)個(gè)的往后挪”這樣的字眼？為什么要一個(gè)個(gè)的挪呢？能不能一大段一大段的挪？打個(gè)比方，如果排序一個(gè)1~100的數(shù)組（原序列是100,99,98...1），這個(gè)時(shí)候100是在第1位，光排完100這個(gè)數(shù)你就得挪99次，得調(diào)用上面的swap方法99次，但比如說把這個(gè)一個(gè)個(gè)挪切換成一半一半的挪，比如第一個(gè)數(shù)100跟51比較后交換然后99跟52比較，是不是就非常大的邁了一大步？這些邁完后，再把間隔變成25，再來邁，雖說可能邁偏對(duì)吧？沒事最后做一個(gè)步伐為1的修正就好了。而這，就是鼎鼎有名的希爾排序。
看一下希爾排序是怎么實(shí)現(xiàn)的哈：
5
歸并排序
看了以前上面一個(gè)個(gè)的挪實(shí)在太費(fèi)勁了，我要比較，我不挪，我直接就拿出來，分成小組，每個(gè)小組自己先弄成有序的，再匯總，這樣這種分而治之思想的實(shí)際上就是歸并排序。它的核心排序點(diǎn)在哪呢？你分治就分治嘛，怎么分？又怎么治？就是我為神馬用這個(gè)排序，這個(gè)數(shù)據(jù)通過這個(gè)方法過一下就變有序了？核心就在于小組——這個(gè)小組的成員最多只有2個(gè)，比如說數(shù)組的長(zhǎng)度是8，就分成了4個(gè)2，7就分成3個(gè)2跟1個(gè)1，多個(gè)數(shù)我們一眼排不出序來，兩個(gè)總可以吧？沒錯(cuò)，這就是分。那怎么治呢？我們看下下面比如說我現(xiàn)在A，B兩個(gè)小組已經(jīng)完成了他們內(nèi)部的排序（他們的長(zhǎng)度都是4）
A B
1568 2479
那一起看看它是怎么實(shí)現(xiàn)的吧：
6
快速排序
這個(gè)時(shí)候呢，也誕生了另一個(gè)思想，個(gè)人看來也是一種分類，它是怎樣的呢？有點(diǎn)類似于體育課的時(shí)候高個(gè)子站后面矮個(gè)子站前面，教練沒辦法一開始就一眼看出誰高誰矮對(duì)吧？那么多人，肯定是隨便逮一個(gè)，來以他為基準(zhǔn)，排序！！！一聲令下，小個(gè)的站這家伙的前邊，大個(gè)的站后邊，對(duì)吧？而這就是快速排序的核心思想。有點(diǎn)像二分法，不過這個(gè)二分法有點(diǎn)不同，它不是按長(zhǎng)度，它是按類，你高就占那邊，矮就站這邊，把整體分成兩部分，那矮的那塊還能不能再分，那是當(dāng)然，矮的那塊再隨便找一個(gè)，再分，這樣就完成了一個(gè)排序的內(nèi)部過程。（左邊小，右邊大，那當(dāng)長(zhǎng)度為3的時(shí)候不就實(shí)現(xiàn)有序了嗎？嗯，這就是快排的核心思想）
具體的代碼怎么實(shí)現(xiàn)呢？
這樣很直觀的我們就想到，嘿我弄兩個(gè)數(shù)組，裝高個(gè)子跟矮個(gè)子，然后再concat回來對(duì)吧？當(dāng)然記得把中間那家伙給放進(jìn)去，別漏了。看下下面：
嗯，是不是很直觀？呵呵，但是要知道，排序，特別是排序數(shù)據(jù)非常多的時(shí)候，最考驗(yàn)的就是性能，而代碼中l(wèi)eft = [], right = []；還遞歸，這個(gè)內(nèi)存的開銷是非常大的，所以我們不這樣，那怎么做呢？
上面的雖然沒重新創(chuàng)建數(shù)組，但是呢？通過交換，比如說大于參考點(diǎn)的放左邊，小于的放右邊，那我直接等待一下，一個(gè)從左邊開始掃描，一個(gè)從右邊，當(dāng)左邊掃描到比參考數(shù)大的數(shù)時(shí)，結(jié)束掃描，右邊也掃描，當(dāng)有一個(gè)數(shù)比參考數(shù)小時(shí)，就結(jié)束掃描，這時(shí)候把這兩個(gè)數(shù)交換一下，是不是就實(shí)現(xiàn)了小的在前面大的在后面，你說，可他們不一定在參考點(diǎn)兩邊啊？沒錯(cuò)，這個(gè)時(shí)候繼續(xù)掃描，等到i和j在某個(gè)點(diǎn)相遇的時(shí)候，把這個(gè)參考點(diǎn)的值跟那個(gè)位置的值換一下，不就實(shí)現(xiàn)兩邊一邊大一邊小嘛。、
嗯，有了一個(gè)了，當(dāng)然得有無數(shù)次，左邊那塊再繼續(xù)做這個(gè)事，右邊的也一樣，當(dāng)右邊跟左邊再加上中間的數(shù)長(zhǎng)度剛好為3或小于3的時(shí)候不就OK了？
7
堆排序
這時(shí)候還有一個(gè)性能也很不錯(cuò)的排序，用到完全二叉樹的方式來的。
它又是怎么想的？臥槽（沒文化的我只會(huì)這一句= =），不就個(gè)排序，非得弄那么多亂七八糟的？嗯，怎么說呢，這是一種思想，先不扯遠(yuǎn)一起看看具體是怎么樣的吧。
堆，有大頂堆跟小頂堆之分，這里就不扯概念了，那個(gè)官方講得很詳細(xì)嗯也很官方= =，簡(jiǎn)單理解一下就是一個(gè)金字塔，你是幫主，你下面還有左右護(hù)法四大天王八大金剛十六羅漢，嗯就這樣一直下去，而所謂的大頂堆就是作為幫主的你是住塔頂?shù)模№敹涯兀縿t相反，你們幫最小最小的那個(gè)小弟就在那。大概是這樣哈：
這個(gè)就是所謂的大頂堆，生活中是不是太常見了？（理解為主，請(qǐng)忽略圖= =）
那它又是怎么做到排序的？
還記得選擇排序是怎么排序的？就是選擇一個(gè)最大數(shù)不斷的插入到最后的對(duì)吧？但是選擇最大數(shù)的那個(gè)過程是通過不斷的比較，一個(gè)個(gè)位置挪動(dòng)去得到的，那能不能跳著走？跳著掃描。實(shí)際上，分成堆只是讓我們更好理解。
一起看看代碼是怎么樣實(shí)現(xiàn)的吧：
下面是做的一個(gè)簡(jiǎn)單的性能測(cè)試
① 普通插入排序與快速排序的速度對(duì)比（數(shù)據(jù)量20萬）：
可以看到在20萬隨機(jī)數(shù)（0-10000）的排序中，快排所花的時(shí)間不足100個(gè)時(shí)間單位，而插入排序要超過50000個(gè)。普通的O(n²)的性能與最好情況O（nlogn）的快排是完全沒法比（數(shù)據(jù)量越龐大結(jié)果越明顯）。
② 希爾排序與快速排序?qū)Ρ龋〝?shù)據(jù)量2000萬）：
由于這兩個(gè)排序都是極不穩(wěn)定的，但是從測(cè)試的幾次結(jié)果看，希爾排序的性能會(huì)略微優(yōu)于快排（語言：JAVAscript）
③歸并排序與希爾排序
歸并排序相對(duì)于希爾，快排的不穩(wěn)定來說，歸并排序最好跟最壞的情況均是nlogn，是穩(wěn)定且快捷的排序算法。利用的正是完全二叉樹的思維模式。
④堆排序與歸并排序
也是2000萬1-10000的隨機(jī)數(shù)排序。
