花了很長時間終于把排序的基礎(chǔ)學(xué)了一下，這段時間學(xué)了很多東西，總結(jié)一下：
學(xué)的排序算法有：插入排序，合并排序，冒泡排序，選擇排序，希爾排序，堆排序，快速排序，計數(shù)排序，基數(shù)排序，桶排序（沒有實(shí)現(xiàn)）。比較一下學(xué)習(xí)后的心得。
我不是很清楚他們的時間復(fù)雜度，也真的不知道他們到底誰快誰慢，因?yàn)闀系耐茖?dǎo)我確實(shí)只是小小了解，并沒有消化。也沒有完全理解他們的精髓，所以又什么錯誤的還需要高手指點(diǎn)。呵呵。
1.普及一下排序穩(wěn)定，所謂排序穩(wěn)定就是指：如果兩個數(shù)相同，對他們進(jìn)行的排序結(jié)果為他們的相對順序不變。例如A={
1,
2,
1,
2,1}這里排序之后是A = {
1,
1,1,
2,
2} 穩(wěn)定就是排序后第一個1就是排序前的第一個1，第二個1就是排序前第二個1，第三個1就是排序前的第三個1。同理2也是一樣。這里用顏色標(biāo)明了。不穩(wěn)定呢就是他們的順序不應(yīng)和開始順序一致。也就是可能會是A={
1,1,
1,
2,
2}這樣的結(jié)果。
2.普及一下原地排序：原地排序就是指不申請多余的空間來進(jìn)行的排序，就是在原來的排序數(shù)據(jù)中比較和交換的排序。例如快速排序，堆排序等都是原地排序，合并排序，計數(shù)排序等不是原地排序。
3.感覺誰最好，在我的印象中快速排序是最好的，時間復(fù)雜度：n*log(n)，不穩(wěn)定排序。原地排序。他的名字很棒，快速嘛。當(dāng)然快了。我覺得他的思想很不錯，分治，而且還是原地排序，省去和很多的空間浪費(fèi)。速度也是很快的，n*log(n)。但是有一個軟肋就是如果已經(jīng)是排好的情況下時間復(fù)雜度就是n*n,不過在加入隨機(jī)的情況下這種情況也得以好轉(zhuǎn)，而且他可以做任意的比較，只要你能給出兩個元素的大小關(guān)系就可以了。適用范圍廣，速度快。
4.插入排序：n*n的時間復(fù)雜度，穩(wěn)定排序，原地排序。插入排序是我學(xué)的第一個排序，速度還是很快的，特別是在數(shù)組已排好了之后，用它的思想來插入一個數(shù)據(jù)，效率是很高的。因?yàn)椴挥萌颗拧Ｋ臄?shù)據(jù)交換也很少，只是數(shù)據(jù)后移，然后放入要插入的數(shù)據(jù)。（這里不是指調(diào)用插入排序，而是用它的思想）。我覺得，在數(shù)據(jù)大部分都排好了，用插入排序會給你帶來很大的方便。數(shù)據(jù)的移動和交換都很少。
5.冒泡排序，n*n的時間復(fù)雜度，穩(wěn)定排序，原地排序。冒泡排序的思想很不錯，一個一個比較，把小的上移，依次確定當(dāng)前最小元素。因?yàn)樗唵危€(wěn)定排序，而且好實(shí)現(xiàn)，所以用處也是比較多的。還有一點(diǎn)就是加上哨兵之后他可以提前退出。
6.選擇排序，n*n的時間復(fù)雜度， 穩(wěn)定排序，原地排序。選擇排序就是冒泡的基本思想，從小的定位，一個一個選擇，直到選擇結(jié)束。他和插入排序是一個相反的過程，插入是確定一個元素的位置，而選擇是確定這個位置的元素。他的好處就是每次只選擇確定的元素，不會對很多數(shù)據(jù)進(jìn)行交換。所以在數(shù)據(jù)交換量上應(yīng)該比冒泡小。
7.插入排序，選擇排序，冒泡排序的比較，他們的時間復(fù)雜度都是n*n。我覺得他們的效率也是差不多的，我個人喜歡冒泡一些，因?yàn)橐盟臅r候數(shù)據(jù)多半不多，而且可以提前的返回已經(jīng)排序好的數(shù)組。而其他兩個排序就算已經(jīng)排好了，他也要做全部的掃描。在數(shù)據(jù)的交換上，冒泡的確比他們都多。呵呵。舉例說明插入一個數(shù)據(jù)在末尾后排序，冒泡只要一次就能搞定，而選擇和插入都必須要n*n的復(fù)雜度才能搞定。就看你怎么看待咯。
8.合并排序：n*log(n)的時間復(fù)雜度， 穩(wěn)定排序，非原地排序。他的思想是分治，先分成小的部分，排好部分之后合并，因?yàn)槲覀兞硗馍暾埖目臻g，在合并的時候效率是0(n)的。速度很快。貌似他的上限是n*log(n)，所以如果說是比較的次數(shù)的話，他比快速排序要少一些。對任意的數(shù)組都能有效地在n*log(n)排好序。但是因?yàn)樗欠窃嘏判颍噪m然他很快，但是貌似他的人氣沒有快速排序高。
9.堆排序：n*log(n)的時間復(fù)雜度， 非穩(wěn)定排序，原地排序。他的思想是利用的堆這種數(shù)據(jù)結(jié)構(gòu)，堆可以看成一個完全二叉樹，所以在排序中比較的次數(shù)可以做到很少。加上他也是原地排序，不需要申請額外的空間，效率也不錯。可是他的思想感覺比快速難掌握一些。還有就是在已經(jīng)排好序的基礎(chǔ)上添加一個數(shù)據(jù)再排序，他的交換次數(shù)和比較次數(shù)一點(diǎn)都不會減少。雖然堆排序在使用的中沒有快速排序廣泛，但是他的數(shù)據(jù)結(jié)構(gòu)和思想真的很不錯，而且用它來實(shí)現(xiàn)優(yōu)先隊(duì)列，效率沒得說。堆，還是要好好學(xué)習(xí)掌握的。
10.希爾排序：n*log(n)的時間復(fù)雜度
(這里是錯誤的，應(yīng)該是n^lamda(1 < lamda < 2), lamda和每次步長選擇有關(guān)。)， 非穩(wěn)定排序，原地排序。主要思想是分治，不過他的分治和合并排序的分治不一樣，他是按步長來分組的，而不是想合并那樣左一半右一半。開始步長為整個的長度的一半。分成nLen/2個組，然后每組排序。接個步長減為原來的一半在分組排序，直到步長為1，排序之后希爾排序就完成了。這個思路很好，據(jù)說是插入排序的升級版，所以在實(shí)現(xiàn)每組排序的時候我故意用了插入排序。我覺得他是一個特別好的排序方法了。他的缺點(diǎn)就是兩個數(shù)可能比較多次，因?yàn)閮蓚€數(shù)據(jù)會多次分不過他們不會出現(xiàn)數(shù)據(jù)的交換。效率也是很高的。
11.快速排序，堆排序，合并排序，希爾排序的比較，他們的時間復(fù)雜的都是n*log(n)，我認(rèn)為在使用上快速排序最廣泛，他原地排序，雖然不穩(wěn)定，可是很多情況下排序根本就不在意他是否穩(wěn)定。他的比較次數(shù)是比較小的，因?yàn)樗褦?shù)據(jù)分成了大和小的兩部分。每次都確定了一個數(shù)的位置，所以理論上說不會出現(xiàn)兩個數(shù)比較兩次的情況，也是在最后在交換數(shù)據(jù)，說以數(shù)據(jù)交換上也很少。合并排序和堆排序也有這些優(yōu)點(diǎn)，但是合并排序要申請額外的空間。堆排序堆已經(jīng)排好的數(shù)據(jù)交換上比快速多。所以目前快速排序用的要廣泛的多。還有他很容易掌握和實(shí)現(xiàn)。
12.計數(shù)排序：n的時間復(fù)雜度，穩(wěn)定排序，非原地排序。他的思想比較新穎，就是先約定數(shù)據(jù)的范圍不是很大，而且數(shù)據(jù)都是整數(shù)(或能定位到整數(shù))的情況，然后直接申請一個空間。把要排序的數(shù)組A的元素值與申請空間B的下標(biāo)對應(yīng)，然后B中存放該下標(biāo)元素值的個數(shù)，從而直接定位A中每個元素的位置。這樣效率只為n。因?yàn)楸容^很特殊，雖然很快，但是用的地方并不多。
13.基數(shù)排序：n的時間復(fù)雜度，穩(wěn)定排序，非原地排序。他的思想是數(shù)據(jù)比較集中在一個范圍，例如都是4位數(shù)，都是5位數(shù)，或數(shù)據(jù)有多個關(guān)鍵字，我們先從各位開始排，然后排十位，依次排到最高位，因?yàn)槲覀兛梢杂靡粋€n的方法排一位，所以總的方法為d*n的復(fù)雜度。關(guān)鍵字也一樣，我們先排第3個關(guān)鍵字，在排第3個關(guān)鍵字，最后排第一個關(guān)鍵字。只有能保證每個關(guān)鍵字在n的時間復(fù)雜度完成，那么整個排序就是一個d*n的時間復(fù)雜度。所以總的速度是很快的。不過有一點(diǎn)就是要確保關(guān)鍵字能在n的時間復(fù)雜度完成。
14.桶排序：n的時間復(fù)雜度，穩(wěn)定排序，非原地排序。主要思路和基數(shù)排序一樣，也是假設(shè)都在一個范圍例如概率都在0-1，而且分布還挺均勻，那么我們也是和基數(shù)排序一樣對一個數(shù)把他劃分在他指定的區(qū)域。然后在連接這些區(qū)域就可以了。書上對每個區(qū)域使用鏈表的存儲，我認(rèn)為在寸小區(qū)域的時候也會有時間在里面。所以只是理論上的n時間復(fù)雜度。這種思路是不錯的。呵呵。
15.計數(shù)排序，基數(shù)排序，桶排序的比較，我覺得他們都很有思想，不過都是在特定情況下才能發(fā)揮最大的效果。雖然效率很高，但是用的不會很廣泛。他們之間我更喜歡計數(shù)排序，來個映射的方式就直接找到了自己的位置，很高明。和基數(shù)排序和同排序只是理論上的n時間復(fù)雜度，基數(shù)排序要確定一個關(guān)鍵字的排序是n復(fù)雜度的，桶排序要確定每個區(qū)域的排序是n復(fù)雜度的。
16.排序算法的最后感悟：黑格爾說過：存在即合理。所以這些排序的算法都是很好的，他確實(shí)給了我們思想上的幫助。感謝前人把精華留給了我們。我得到的收獲很大，總結(jié)一下各自排序的收獲：
冒泡：好實(shí)現(xiàn)，速度不慢，使用于輕量級的數(shù)據(jù)排序。
插入排序：也使用于小數(shù)據(jù)的排序，但是我從他的思想中學(xué)到怎么插入一個數(shù)據(jù)。呵呵，這樣就知道在排好的數(shù)據(jù)里面，不用再排序了，而是直接調(diào)用一下插入就可以了。
選擇排序：我學(xué)會了怎么去獲得最大值，最小值等方法。只要選擇一下，不就可以了。
合并排序：我學(xué)會分而治之的方法，而且在合并兩個數(shù)組的時候很適用。
堆排序：可以用它來實(shí)現(xiàn)優(yōu)先隊(duì)列，而且他的思想應(yīng)該給我加了很多內(nèi)力。
快速排序：本來就用的最多的排序，對我的幫助大的都不知道怎么說好。
希爾排序：也是分治，讓我看到了分治的不同，原來還有這種思想的存在。
計數(shù)排序，基數(shù)排序，桶排序：特殊情況特殊處理。
附上我學(xué)習(xí)這里排序的連接
快速排序?qū)W習(xí)1 快速排序?qū)W習(xí)2（隨機(jī)化版本）
快速排序?qū)W習(xí)3（最初版） 快速排序?qū)W習(xí)4（最初版加隨機(jī)版）
插入排序 冒泡排序 選擇排序
希爾排序 合并排序 堆排序 用堆實(shí)現(xiàn)優(yōu)先隊(duì)列
基數(shù)排序 計數(shù)排序