原創(chuàng)文章，轉(zhuǎn)載請(qǐng)注明出處
1. 排序算法簡(jiǎn)介
提起排序算法，相信大家并不陌生痢甘。最常見(jiàn)也是最基礎(chǔ)的有：插入排序宪拥，選擇排序，冒泡排序窃蹋。這三種排序的平均復(fù)雜度都是卡啰，實(shí)現(xiàn)起來(lái)簡(jiǎn)單，在小規(guī)模排序中有大量的應(yīng)用警没。其中插入排序由于其是穩(wěn)定的匈辱、原地的排序而受到廣大群眾的歡迎。在其基礎(chǔ)上衍生出來(lái)的高級(jí)版本---"希爾排序"則是效率更高的插入排序杀迹。
但是如果數(shù)據(jù)量非常大亡脸，的時(shí)間復(fù)雜度我們似乎也不太能接受，這樣我們又引申出了一些時(shí)間復(fù)雜度為
的排序算法，其中最常見(jiàn)的就是我們今天的兩個(gè)主角：歸并排序與快速排序浅碾。
再往上走大州，似乎的算法也不太滿足我們了。別擔(dān)心垂谢，我們還有
的算法---桶排序厦画、計(jì)數(shù)排序等。這一類(lèi)算法做到了線性的時(shí)間復(fù)雜度滥朱，效率非常高根暑，但是其對(duì)數(shù)據(jù)的要求也相應(yīng)提高，并不是所有情況都可以使用焚虱。
2. 為什么要使用這種排序算法购裙？
現(xiàn)在我們對(duì)常見(jiàn)的排序算法有了一定的認(rèn)識(shí)，那我們應(yīng)該如何來(lái)評(píng)判一個(gè)排序算法的好壞呢鹃栽？在特定的情況下躏率，我們又該如何選擇合適的算法呢？
通常來(lái)看民鼓，我認(rèn)為選擇排序算法時(shí)有幾點(diǎn)需要考慮：
- 時(shí)間復(fù)雜度薇芝。大多數(shù)情況下，這是一個(gè)決定性的因素丰嘉，至少可以幫助我們篩選掉大部分算法夯到。
-
空間復(fù)雜度。雖然現(xiàn)在的內(nèi)存不值錢(qián)了饮亏，而且得益于大部分語(yǔ)言都有的垃圾清除機(jī)制耍贾，空間復(fù)雜度可能不是我們首先需要考慮的條件。但是當(dāng)算法的空間使用量超出我們所希望的閾值路幸，甚至頻繁觸發(fā)了GC荐开，那我們就需要進(jìn)行仔細(xì)的評(píng)估了。PS: 對(duì)于空間復(fù)雜度為
的排序算法我們稱之為原地排序简肴。
-
算法的穩(wěn)定性晃听。這里的穩(wěn)定性指的是元素之間的順序的穩(wěn)定性，舉個(gè)例子：
1,8,3,2,8,6
對(duì)于這樣一串?dāng)?shù)字砰识，我們按照從小到大進(jìn)行排序：
1,2,3,6,8,8
在原數(shù)組中能扒，存在兩個(gè)相同的元素8，一個(gè)在前一個(gè)在后辫狼，那么對(duì)于排序以后的數(shù)組初斑，如果這兩個(gè)8的先后位置沒(méi)有改變，那么這次排序是穩(wěn)定的膨处。
可能有朋友會(huì)覺(jué)得越平，這兩個(gè)8位置變不變有什么關(guān)系频蛔，反正都一樣。我們可以思考一下秦叛，如果我們排序的不是數(shù)字晦溪，而是一個(gè)對(duì)象。假如我們按照對(duì)象的A屬性對(duì)其排序挣跋，但是又希望在A屬性相同的條件下三圆，不改變?nèi)萜髦袑?duì)象之間原有的順序。這時(shí)算法的穩(wěn)定性就是一個(gè)重要的指標(biāo)了避咆。
實(shí)際場(chǎng)景中舟肉，在對(duì)名字、手機(jī)號(hào)碼等進(jìn)行排序時(shí)查库，我們往往會(huì)需要一個(gè)穩(wěn)定的算法路媚。 -
數(shù)據(jù)規(guī)模。私以為這一點(diǎn)的重要性不亞于時(shí)間復(fù)雜度樊销，而且往往有一票否決權(quán)整慎。如果我們?cè)跀?shù)據(jù)量非常小的時(shí)候還是不顧一切選擇快排，那么快排中選擇pivot的操作所占的比重將會(huì)超出我們的預(yù)期围苫，導(dǎo)致其效率可能還不如O(n^2)的算法裤园。
同樣舉個(gè)例子，我們?cè)贘ava開(kāi)發(fā)中剂府，對(duì)于數(shù)據(jù)的排序拧揽，只需要來(lái)一行Arrays.sort()就可以了，但是我們有沒(méi)有思考過(guò)腺占，為什么無(wú)論數(shù)據(jù)量大小淤袜，Arrays.sort()都能很快的運(yùn)行？它用的究竟是什么鬼才算法衰伯？
源碼這里就不貼了饮怯，有興趣的朋友可以自行查看。這里我只將其中的主要邏輯進(jìn)行列舉（JDK 1.8）:
- 數(shù)據(jù)量小于47嚎研，使用插入排序。
- 數(shù)據(jù)量小于286库倘，使用快排临扮。
- 根據(jù)數(shù)據(jù)情況再選擇使用快排還是歸并排序。
可以看到強(qiáng)如Arrays.sort()這樣的工業(yè)級(jí)排序函數(shù)教翩，也并非是靠一個(gè)算法吃到底杆勇。
在什么情況下用什么工具？為什么要用饱亿？是我們?cè)诰幊踢^(guò)程中要不斷問(wèn)自己的兩個(gè)問(wèn)題蚜退。
