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