一始衅、直接插入排序
直接插入排序(Insertion Sort)的基本思想是：每次將一個(gè)待排序的元素記錄噩翠，按其關(guān)鍵字大小插入到它前面已經(jīng)排好序的子序列中的適當(dāng)位置烹俗，直到全部元素插入完成為止蛤袒。
設(shè)需要排序的數(shù)組為a[0…n-1]鸟蜡。
1. 初始時(shí)，i = 0豌注，a[0]自成1個(gè)有序區(qū)伤塌，無(wú)序區(qū)為a[1..n-1]。
2. 將a[i]并入當(dāng)前的有序區(qū)a[0…i-1]中形成a[0…i]的有序區(qū)間轧铁。
3. i++并重復(fù)第二步直到 i == n-1每聪，排序完成。
這里齿风，我將a[i]并入當(dāng)前的有序區(qū)時(shí)药薯，設(shè)置了一個(gè)臨時(shí)變量 tmp 用于交換兩個(gè)無(wú)序元素，這樣簡(jiǎn)化了代碼救斑。
時(shí)間復(fù)雜度&空間復(fù)雜度
如果目標(biāo)是把n個(gè)元素的序列按序排列童本，那么采用插入排序存在最好情況和最壞情況。最好情況就是脸候，序列已經(jīng)是升序排列了穷娱，在這種情況下，需要進(jìn)行的比較操作需(n - 1)次即可运沦。最壞情況就是泵额，序列是降序排列，那么此時(shí)需要進(jìn)行的比較共有n(n - 1) / 2次茶袒。插入排序的賦值操作是比較操作的次數(shù)減去(n - 1)次梯刚。平均來(lái)說(shuō)插入排序算法復(fù)雜度為O(n2)。因而薪寓，插入排序不適合對(duì)于數(shù)據(jù)量比較大的排序應(yīng)用。但是澜共，如果需要排序的數(shù)據(jù)量很小向叉，例如，量級(jí)小于千嗦董，那么插入排序還是一個(gè)不錯(cuò)的選擇母谎。
這里再介紹另外一個(gè)排序算法概念，穩(wěn)定性：假定在待排序的序列中京革，存在多個(gè)具有相同的關(guān)鍵字的元素奇唤，若經(jīng)過(guò)排序幸斥，這些元素的相對(duì)次序保持不變，即在原序列中咬扇，a[1] = a[j]甲葬，且 a[i] 在 a[j] 之前，而在排序后的序列中懈贺，a[i] 仍在 a[j] 之前经窖，則稱這種排序算法是穩(wěn)定的;否則稱為不穩(wěn)定的。在簡(jiǎn)單插入排序中只有當(dāng)兩個(gè)無(wú)序的元素不相等時(shí)梭灿，才會(huì)進(jìn)行交換画侣，所以相等元素的相對(duì)位置不會(huì)改變。
二堡妒、希爾排序
希爾排序(Shell Sort)又稱為“縮小增量排序”配乱。該方法的基本思想是：先將整個(gè)待排元素序列分割成若干個(gè)子序列(由相隔某個(gè)“增量”的元素組成的)分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序皮迟，待整個(gè)序列中的元素基本有序(增量足夠小宪卿，例如為1)時(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序万栅。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下(接近最好情況)佑钾，效率是很高的，因此希爾排序在時(shí)間效率上比前一種方法有較大提高烦粒。
基本步驟休溶，在此我們選擇增量gap=n/2，縮小增量繼續(xù)以gap = gap/2的方式扰她，這種增量選擇我們可以用一個(gè)序列來(lái)表示兽掰，{n/2,(n/2)/2...1}，稱為增量序列徒役。希爾排序的增量序列的選擇與證明是個(gè)數(shù)學(xué)難題孽尽，我選擇的這個(gè)增量序列是比較常用的，也是希爾建議的增量忧勿，稱為希爾增量杉女，但其實(shí)這個(gè)增量序列不是最優(yōu)的。此處我們做示例使用希爾增量鸳吸。
希爾排序中熏挎，由于相同元素可能被分于不同排序組中，所以它們的相對(duì)位置很可能發(fā)生變化晌砾，如上圖中的 25 坎拐，所以希爾排序算法是一種不穩(wěn)定的算法。
希爾排序在數(shù)組中采用跳躍式分組的策略，通過(guò)某個(gè)增量將數(shù)組元素劃分為若干組哼勇，然后分組進(jìn)行插入排序都伪，隨后逐步縮小增量，繼續(xù)按組進(jìn)行插入排序操作积担，直至增量為1陨晶。希爾排序通過(guò)這種策略使得整個(gè)數(shù)組在初始階段達(dá)到從宏觀上看基本有序，小的基本在前磅轻，大的基本在后珍逸。然后縮小增量，到增量為1時(shí)聋溜，其實(shí)多數(shù)情況下只需微調(diào)即可谆膳，不會(huì)涉及過(guò)多的數(shù)據(jù)移動(dòng)。
上面選擇的增量序列{n/2,(n/2)/2...1}(希爾增量)撮躁，其最壞時(shí)間復(fù)雜度依然為O(n2)漱病，一些經(jīng)過(guò)優(yōu)化的增量序列如代碼中的方法經(jīng)過(guò)復(fù)雜證明可使得最壞時(shí)間復(fù)雜度為O(n3/2)。
三把曼、選擇排序
選擇排序的思想：從所有序列中先找到最小的杨帽，然后放到第一個(gè)位置。之后再看剩余元素中最小的嗤军，放到第二個(gè)位置……以此類推注盈，就可以完成整個(gè)的排序工作⌒鹱可以很清楚的發(fā)現(xiàn)老客，選擇排序是固定位置，找元素震叮。相比于插入排序的固定元素找位置胧砰，是兩種思維方式。
基這種思想苇瓣，我做出了一步優(yōu)化尉间，同時(shí)將無(wú)序序列中的最大最小值找出來(lái)，放到有序序列的頭和尾击罪，簡(jiǎn)單來(lái)說(shuō)就是從所有序列中先找到最小和最大的的哲嘲，然后最小的放到第一個(gè)位置，最大的放到最后一個(gè)位置外邓。之后再看剩余元素中最小的和最大的撤蚊，放到第二個(gè)位置和倒數(shù)第二個(gè)位置……以此類推，也可以完成整個(gè)的排序工作损话。而且比前一種更快。
從選擇排序的思想或者是上面的代碼中，我們都不難看出丧枪，尋找最小的元素需要一個(gè)循環(huán)的過(guò)程光涂，而排序又是需要一個(gè)循環(huán)的過(guò)程。因此顯而易見(jiàn)拧烦，這個(gè)算法的時(shí)間復(fù)雜度也是O(n*n)的忘闻。這就意味值在n比較小的情況下，算法可以保證一定的速度恋博，當(dāng)n足夠大時(shí)齐佳，算法的效率會(huì)降低。并且隨著n的增大债沮，算法的時(shí)間增長(zhǎng)很快炼吴。
傳統(tǒng)的簡(jiǎn)單選擇排序,每趟循環(huán)只能確定一個(gè)元素排序后的定位。我們可以考慮改進(jìn)為每趟循環(huán)確定兩個(gè)元素(當(dāng)前趟最大和最小記錄)的位置,從而減少排序所需的循環(huán)次數(shù)疫衩。改進(jìn)后對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序,最多只需進(jìn)行[n/2]趟循環(huán)即可硅蹦。由以上分析易知選擇排序的依然不穩(wěn)定。
四闷煤、堆排序
堆排序的思想(以大頂堆為例)：
利用堆頂記錄的是最大關(guān)鍵字這一特性童芹，每一輪取堆頂元素放入有序區(qū)，就類似選擇排序每一輪選擇一個(gè)最大值放入有序區(qū)鲤拿，可以把堆排序看成是選擇排序的改進(jìn)假褪。
將初始待排序關(guān)鍵字序列(R0,R1,R2....Rn)構(gòu)建成大頂堆，此堆為初始的無(wú)序區(qū);
將堆頂元素R[0]與最后一個(gè)元素R[n]交換近顷，此時(shí)得到新的無(wú)序區(qū)(R0,R1,R2,......Rn-1)和新的有序區(qū)(Rn);
由于交換后新的堆頂R[0]可能違反堆的性質(zhì)生音，因此需要對(duì)當(dāng)前無(wú)序區(qū)(R0,R1,R2,......Rn-1)調(diào)整為新堆。
不斷重復(fù)此2幕庐、3步驟直到有序區(qū)的元素個(gè)數(shù)為n-1久锥，則整個(gè)排序過(guò)程完成。
由以上分析易知堆排序也不穩(wěn)定异剥。由二叉樹的特點(diǎn)知道它的空間復(fù)雜度為O(N*logN)
五瑟由、冒泡排序
冒泡排序(Bubble Sort)是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列冤寿，一次比較兩個(gè)元素歹苦，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換督怜，也就是說(shuō)該數(shù)列已經(jīng)排序完成殴瘦。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
步驟：
1.比較相鄰的元素号杠。如果第一個(gè)比第二個(gè)大蚪腋，就交換他們兩個(gè)丰歌。
2.對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)屉凯。在這一點(diǎn)立帖，最后的元素應(yīng)該會(huì)是最大的數(shù)。
3.針對(duì)所有的元素重復(fù)以上的步驟悠砚，除了最后一個(gè)晓勇。
4.持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較灌旧。
冒泡排序是一種穩(wěn)定的排序算法绑咱，它的最壞情況和平均復(fù)雜度是O(n2)，甚至連插入排序(O(n2)算法復(fù)雜度)效率都比冒泡排序算法更好枢泰，唯一的優(yōu)勢(shì)在于基于它的改進(jìn)算法——快速排序算法描融。
六、快速排序
快速排序是冒泡排序的一種改進(jìn)宗苍，冒泡排序排完一趟是最大值冒出來(lái)了稼稿，那么可不可以先選定一個(gè)值，然后掃描待排序序列讳窟，把小于該值的記錄和大于該值的記錄分成兩個(gè)單獨(dú)的序列让歼，然后分別對(duì)這兩個(gè)序列進(jìn)行上述操作。這就是快速排序丽啡，我們把選定的那個(gè)值稱為樞紐值谋右，如果樞紐值為序列中的最大值，那么一趟快速排序就變成了一趟冒泡排序补箍。
快速排序使用分治法(Divide and conquer)策略來(lái)把一個(gè)串行(list)分為兩個(gè)子串行(sub-lists)改执。
步驟為：(1)從數(shù)列中挑出一個(gè)元素，稱為 "基準(zhǔn)"(pivot);
(2)重新排序數(shù)列坑雅，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面辈挂，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊)。在這個(gè)分區(qū)退出之后裹粤，該基準(zhǔn)就處于數(shù)列的中間位置终蒂。這個(gè)稱為分區(qū)(partition)操作。
(3)遞歸地(recursive)把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序遥诉。
當(dāng)我們每次劃分的時(shí)候選擇的基準(zhǔn)數(shù)接近于整組數(shù)據(jù)的最大值或者最小值時(shí)拇泣，快速排序就會(huì)發(fā)生最壞的情況，但是每次選擇的基準(zhǔn)數(shù)都接近于最大數(shù)或者最小數(shù)的概率隨著排序元素的增多就會(huì)越來(lái)越小矮锈，我們完全可以忽略這種情況霉翔。但是在數(shù)組有序的情況下，它也會(huì)發(fā)生最壞的情況苞笨，為了避免這種情況债朵，我們?cè)谶x擇基準(zhǔn)數(shù)的時(shí)候可以采用三數(shù)取中法來(lái)選擇基準(zhǔn)數(shù)子眶。
三數(shù)取中法： 選擇這組數(shù)據(jù)的第一個(gè)元素、中間的元素葱弟、最后一個(gè)元素壹店，這三個(gè)元素里面值居中的元素作為基準(zhǔn)數(shù)猜丹。
按照以上思想可以容易實(shí)現(xiàn)一下代碼：
遞歸的最底部情形芝加，是數(shù)列的大小是零或一冯乘，也就是永遠(yuǎn)都已經(jīng)被排序好了兰绣。雖然一直遞歸下去空扎，但是這個(gè)算法總會(huì)退出恋脚，因?yàn)樵诿看蔚牡?iteration)中效扫，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去庆揪。小區(qū)間優(yōu)化：當(dāng)劃分的子序列很小的時(shí)候(一般認(rèn)為小于13個(gè)元素左右時(shí))莉恼，我們?cè)谑褂每焖倥判驅(qū)@些小序列排序反而不如直接插入排序高效咕村。因?yàn)榭焖倥判驅(qū)?shù)組進(jìn)行劃分最后就像一顆二叉樹一樣艾疟，當(dāng)序列小于13個(gè)元素時(shí)我們?cè)偈褂每炫诺脑捑拖喈?dāng)于增加了二叉樹的最后幾層的結(jié)點(diǎn)數(shù)目来吩，遞歸的次數(shù)就會(huì)驟增。所以我們?cè)诋?dāng)子序列小于13個(gè)元素的時(shí)候就改用直接插入排序來(lái)對(duì)這些子序列進(jìn)行排序蔽莱。
根據(jù)上面的一些思想弟疆，我們對(duì)快速排序的實(shí)現(xiàn)共有如下幾種方法：
實(shí)現(xiàn)方式一：左右分治法
算法思想：在待排序序列中選擇一個(gè)數(shù)據(jù)作為基準(zhǔn)值(三數(shù)取中法選擇基準(zhǔn)值)，定義兩個(gè)變量left,right開(kāi)始分別記錄待排序區(qū)間的兩端的值盗冷，左變量向右找比基準(zhǔn)值大的數(shù)據(jù)怠苔，找到后停下來(lái)，接著右變量向左開(kāi)始找比基準(zhǔn)值小的數(shù)據(jù)仪糖，找到后停下來(lái)柑司，交換左右變量所記錄的數(shù)據(jù)，直到兩指針相遇锅劝，出循環(huán)后將左變量值與基準(zhǔn)值進(jìn)行交換攒驰，交換成功后比基準(zhǔn)值小的數(shù)據(jù)都在其左邊，比基準(zhǔn)值大的數(shù)據(jù)都在基準(zhǔn)值的右邊故爵，換言之基準(zhǔn)值已經(jīng)處于合適的位置玻粪。接著遞歸對(duì)基準(zhǔn)值的左區(qū)間和右區(qū)間進(jìn)行排序，當(dāng)區(qū)間只有一個(gè)數(shù)據(jù)時(shí)稠集，默認(rèn)已經(jīng)有序奶段。
實(shí)現(xiàn)方式二：挖坑法
算法思想：在待排序序列中選擇一個(gè)數(shù)據(jù)作為基準(zhǔn)值(暫且將區(qū)間右端數(shù)據(jù)作為基準(zhǔn)值)，首次將坑設(shè)在基準(zhǔn)值處剥纷，定義兩個(gè)變量left,right開(kāi)始分別記錄待排序區(qū)間的兩端痹籍，左變量向右找比基準(zhǔn)值大的數(shù)據(jù)，找到后將該值填入坑中并且將坑的位置更新在左變量所記錄的位置晦鞋，接著右變量向左開(kāi)始找比基準(zhǔn)值小的數(shù)據(jù)蹲缠，找到后將該值填入坑中并且將坑的位置更新在右變量記錄的位置棺克，直到兩變量相遇，出循環(huán)后比基準(zhǔn)值小的數(shù)據(jù)都在其左邊线定，比基準(zhǔn)值大的數(shù)據(jù)都在基準(zhǔn)值的右邊娜谊，換言之基準(zhǔn)值已經(jīng)處于合適的位置。接著遞歸對(duì)基準(zhǔn)值的左區(qū)間和右區(qū)間進(jìn)行排序斤讥，當(dāng)區(qū)間只有一個(gè)數(shù)據(jù)時(shí)纱皆，默認(rèn)已經(jīng)有序。
算法實(shí)現(xiàn)3：前后指針?lè)?/p>
算法思想：在待排序序列中選擇一個(gè)數(shù)據(jù)作為基準(zhǔn)值(暫且將區(qū)間右端數(shù)據(jù)作為基準(zhǔn)值)芭商，定義兩個(gè)臨時(shí)變量prev和cur,cur首次記錄待排序區(qū)間的第一個(gè)元素派草，prev指向cur的前一個(gè)位置，只要cur沒(méi)走到區(qū)間末尾铛楣，就在中間找比基準(zhǔn)值小的數(shù)據(jù)近迁，每找到一次將prev記錄的位置下標(biāo)加一，然后如果二者所指元素不同就將其所指元素交換簸州，直到cur走到區(qū)間的最右端退出循環(huán)鉴竭，之后將prev++,將cur和prev所記錄的數(shù)據(jù)進(jìn)行交換。至此基準(zhǔn)值被排序到正確位置岸浑，遞歸其左右區(qū)間即可完成整個(gè)排序搏存。
快速排序是一種快速的分而治之的算法，它是已知的最快的排序算法助琐，其平均運(yùn)行時(shí)間為O(N*1ogN) 祭埂。它的速度主要?dú)w功于一個(gè)非長(zhǎng)緊湊的并且高度優(yōu)化的內(nèi)部循環(huán)。但是他也是一種不穩(wěn)定的排序兵钮，當(dāng)基準(zhǔn)數(shù)選擇的不合理的時(shí)候他的效率又會(huì)編程O(N*N)蛆橡。快速排序的最好情況： 快速排序的最好情況是每次都劃分后左右子序列的大小都相等掘譬，其運(yùn)行的時(shí)間就為O(N*1ogN)泰演。快速排序的最壞情況： 快速排序的最壞的情況就是當(dāng)分組重復(fù)生成一個(gè)空序列的時(shí)候葱轩，這時(shí)候其運(yùn)行時(shí)間就變?yōu)镺(N*N)快速排序的平均情況： 平均情況下是O(N*logN)睦焕。
快速排序非遞歸
思想同遞歸，只是要借助額外空間來(lái)臨時(shí)存儲(chǔ)待排序區(qū)間的首尾元素值靴拱。
七垃喊、歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個(gè)非常典型的應(yīng)用袜炕。
歸并排序基本思想：設(shè)兩個(gè)有序的子序列(相當(dāng)于輸入序列)放在同一序列中相鄰的位置上：a[begin1...end1]本谜，a[begin2...end2]，先將它們合并到一個(gè)局部的暫存序列 temp (相當(dāng)于輸出序列)中偎窘，待合并完成后將 temp 復(fù)制回 a[begin...end]中乌助，從而完成排序溜在。 在具體的合并過(guò)程中，設(shè)置begin1他托，begin2 和 index三個(gè)變量掖肋，其初值分別記錄這三個(gè)記錄區(qū)的起始位置。合并時(shí)依次比較 a[begin1] 和 a[begin2] 的關(guān)鍵字赏参，取關(guān)鍵字較小(或較大)的記錄復(fù)制到 temp[index] 中志笼，然后將被復(fù)制記錄的變量begin1 或 begin2 加 1，以及指向復(fù)制位置的變量 index加 1登刺。重復(fù)這一過(guò)程直至兩個(gè)輸入的子序列有一個(gè)已全部復(fù)制完畢(不妨稱其為空)籽腕，此時(shí)將另一非空的子序列中剩余記錄依次復(fù)制到 a中即可。
歸并排序是一種穩(wěn)定的排序且效率是比較高的纸俭，設(shè)數(shù)列長(zhǎng)為N，將數(shù)列分開(kāi)成小數(shù)列一共要logN步南窗，每步都是一個(gè)合并有序數(shù)列的過(guò)程揍很，時(shí)間復(fù)雜度可以記為O(N)，故一共為O(N*logN)万伤。因?yàn)闅w并排序每次都是在相鄰的數(shù)據(jù)中進(jìn)行操作窒悔，所以歸并排序在O(N*logN)的幾種排序方法(快速排序，歸并排序敌买，希爾排序简珠，堆排序)也是效率比較高的。
