本文的整理基于：http://blog.csdn.net/hguisu/article/details/7776068
排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過(guò)程中需要訪問(wèn)外存。
我們這里說(shuō)說(shuō)八大排序就是內(nèi)部排序。
當(dāng)n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。
快速排序：是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短；
1. 插入排序—直接插入排序(Straight Insertion Sort)
基本思想:
將一個(gè)記錄插入到已排序好的有序表中，從而得到一個(gè)新，記錄數(shù)增1的有序表。即：先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入，直至整個(gè)序列有序?yàn)橹埂?/p>
要點(diǎn)：設(shè)立哨兵，作為臨時(shí)存儲(chǔ)和判斷數(shù)組邊界之用。
直接插入排序示例：
如果碰見(jiàn)一個(gè)和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒(méi)有改變，從原無(wú)序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。
效率：
時(shí)間復(fù)雜度：O（n^2）.
2. 插入排序—希爾排序（Shell`s Sort）
希爾排序是1959 年由D.L.Shell 提出來(lái)的，相對(duì)直接排序有較大的改進(jìn)。希爾排序又叫縮小增量排序。
基本思想：
先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。
操作方法：
1. 選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；
3. 每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。
先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序，待整個(gè)序列中的元素基本有序（增量足夠?。r(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況），效率是很高的，因此希爾排序在時(shí)間效率上比前兩種方法有較大提高。
希爾排序時(shí)效分析很難，關(guān)鍵碼的比較次數(shù)與記錄移動(dòng)次數(shù)依賴于增量因子序列d的選取，特定情況下可以準(zhǔn)確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動(dòng)次數(shù)。目前還沒(méi)有人給出選取最好的增量因子序列的方法。增量因子序列可以有各種取法，有取奇數(shù)的，也有取質(zhì)數(shù)的，但需要注意：增量因子中除1 外沒(méi)有公因子，且最后一個(gè)增量因子必須為1。希爾排序方法是一個(gè)不穩(wěn)定的排序方法。
3. 選擇排序—簡(jiǎn)單選擇排序（Simple Selection Sort）
基本思想：
在要排序的一組數(shù)中，選出最?。ɑ蛘咦畲螅┑囊粋€(gè)數(shù)與第1個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最?。ɑ蛘咦畲螅┑呐c第2個(gè)位置的數(shù)交換，依次類推，直到第n-1個(gè)元素（倒數(shù)第二個(gè)數(shù)）和第n個(gè)元素（最后一個(gè)數(shù)）比較為止。
操作方法：
第一趟，從n 個(gè)記錄中找出關(guān)鍵碼最小的記錄與第一個(gè)記錄交換；
第二趟，從第二個(gè)記錄開(kāi)始的n-1 個(gè)記錄中再選出關(guān)鍵碼最小的記錄與第二個(gè)記錄交換；
以此類推.....
第i 趟，則從第i 個(gè)記錄開(kāi)始的n-i+1 個(gè)記錄中選出關(guān)鍵碼最小的記錄與第i 個(gè)記錄交換，
直到整個(gè)序列按關(guān)鍵碼有序。
在簡(jiǎn)單選擇排序過(guò)程中，所需移動(dòng)記錄的次數(shù)比較少。最好情況下，即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了，則不需要移動(dòng)記錄。
最壞情況下，即待排序記錄初始狀態(tài)是按第一條記錄最大，之后的記錄從小到大順序排列，則需要移動(dòng)記錄的次數(shù)最多為3（n-1）。簡(jiǎn)單選擇排序過(guò)程中需要進(jìn)行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況無(wú)關(guān)。當(dāng)i=1時(shí)，需進(jìn)行n-1次比較；當(dāng)i=2時(shí)，需進(jìn)行n-2次比較；依次類推，共需要進(jìn)行的比較次數(shù)是(n-1)+(n-2)+…+2+1=n(n-1)/2，即進(jìn)行比較操作的時(shí)間復(fù)雜度為O(n^2)，進(jìn)行移動(dòng)操作的時(shí)間復(fù)雜度為O(n)。
簡(jiǎn)單選擇排序是不穩(wěn)定排序。
簡(jiǎn)單選擇排序的改進(jìn)——二元選擇排序
簡(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)即可。具體實(shí)現(xiàn)如下：
4. 選擇排序—堆排序（Heap Sort）
堆排序是一種樹(shù)形選擇排序，是對(duì)直接選擇排序的有效改進(jìn)。
基本思想：
堆的定義如下：具有n個(gè)元素的序列（k1,k2,...,kn),當(dāng)且僅當(dāng)滿足：
稱之為堆。由堆的定義可以看出，堆頂元素（即第一個(gè)元素）必為最小項(xiàng)（小頂堆）。
若以一維數(shù)組存儲(chǔ)一個(gè)堆，則堆對(duì)應(yīng)一棵完全二叉樹(shù)，且所有非葉結(jié)點(diǎn)的值均不大于(或不小于)其子女的值，根結(jié)點(diǎn)（堆頂元素）的值是最小(或最大)的。如：
(a) 大頂堆序列：（96,83,27,38,11,09)
(b) 小頂堆序列：（12,36,24,85,47,30,53,91）
5. 交換排序—冒泡排序（Bubble Sort）
基本思想：
在要排序的一組數(shù)中，對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對(duì)相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換。
6. 交換排序—快速排序（Quick Sort）
基本思想：
1）選擇一個(gè)基準(zhǔn)元素,通常選擇第一個(gè)元素或者最后一個(gè)元素,
2）通過(guò)一趟排序?qū)⒋判虻挠涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的元素值均比基準(zhǔn)元素值小。另一部分記錄的元素值比基準(zhǔn)值大。
3）此時(shí)基準(zhǔn)元素在其排好序后的正確位置
4）然后分別對(duì)這兩部分記錄用同樣的方法繼續(xù)進(jìn)行排序，直到整個(gè)序列有序。
快速排序的示例：
分析：
快速排序是通常被認(rèn)為在同數(shù)量級(jí)（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按關(guān)鍵碼有序或基本有序時(shí)，快排序反而蛻化為冒泡排序。為改進(jìn)之，通常以“三者取中法”來(lái)選取基準(zhǔn)記錄，即將排序區(qū)間的兩個(gè)端點(diǎn)與中點(diǎn)三個(gè)記錄關(guān)鍵碼居中的調(diào)整為支點(diǎn)記錄。快速排序是一個(gè)不穩(wěn)定的排序方法。
7. 歸并排序（Merge Sort）
基本思想：
歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。
歸并排序示例：
合并方法：
設(shè)r[i…n]由兩個(gè)有序子表r[i…m]和r[m+1…n]組成，兩個(gè)子表長(zhǎng)度分別為n-i +1、n-m。
j=m+1；k=i；i=i; //置兩個(gè)子表的起始下標(biāo)及輔助數(shù)組的起始下標(biāo)
若i>m 或j>n，轉(zhuǎn)⑷ //其中一個(gè)子表已合并完，比較選取結(jié)束
//選取r[i]和r[j]較小的存入輔助數(shù)組rf
如果r[i]
否則，rf[k]=r[j]； j++； k++； 轉(zhuǎn)⑵
//將尚未處理完的子表中元素存入rf
如果i<=m，將r[i…m]存入rf[k…n] //前一子表非空
如果j<=n , ?將r[j…n] 存入rf[k…n] //后一子表非空
合并結(jié)束。
8. 桶排序/基數(shù)排序(Radix Sort)
說(shuō)基數(shù)排序之前，我們先說(shuō)桶排序：
基本思想：是將陣列分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞回方式繼續(xù)使用桶排序進(jìn)行排序）。桶排序是鴿巢排序的一種歸納結(jié)果。當(dāng)要被排序的陣列內(nèi)的數(shù)值是均勻分配的時(shí)候，桶排序使用線性時(shí)間（Θ（n））。但桶排序并不是比較排序，他不受到 O(n log n) 下限的影響。
簡(jiǎn)單來(lái)說(shuō)，就是把數(shù)據(jù)分組，放在一個(gè)個(gè)的桶中，然后對(duì)每個(gè)桶里面的在進(jìn)行排序。
例如要對(duì)大小為[1..1000]范圍內(nèi)的n個(gè)整數(shù)A[1..n]排序
首先，可以把桶設(shè)為大小為10的范圍，具體而言，設(shè)集合B[1]存儲(chǔ)[1..10]的整數(shù)，集合B[2]存儲(chǔ) ? (10..20]的整數(shù)，……集合B[i]存儲(chǔ)( ? (i-1)*10, ? i*10]的整數(shù)，i ? = ? 1,2,..100?？偣灿? 100個(gè)桶。
然后，對(duì)A[1..n]從頭到尾掃描一遍，把每個(gè)A[i]放入對(duì)應(yīng)的桶B[j]中。再對(duì)這100個(gè)桶中每個(gè)桶里的數(shù)字排序，這時(shí)可用冒泡，選擇，乃至快排，一般來(lái)說(shuō)任何排序法都可以。
最后，依次輸出每個(gè)桶里面的數(shù)字，且每個(gè)桶中的數(shù)字從小到大輸出，這樣就得到所有數(shù)字排好序的一個(gè)序列了。
假設(shè)有n個(gè)數(shù)字，有m個(gè)桶，如果數(shù)字是平均分布的，則每個(gè)桶里面平均有n/m個(gè)數(shù)字。如果
對(duì)每個(gè)桶中的數(shù)字采用快速排序，那么整個(gè)算法的復(fù)雜度是
O(n?? + ? m ? * ? n/m*log(n/m)) ? = ? O(n?? + ? nlogn ? - ? nlogm)
從上式看出，當(dāng)m接近n的時(shí)候，桶排序復(fù)雜度接近O(n)
當(dāng)然，以上復(fù)雜度的計(jì)算是基于輸入的n個(gè)數(shù)字是平均分布這個(gè)假設(shè)的。這個(gè)假設(shè)是很強(qiáng)的? ，實(shí)際應(yīng)用中效果并沒(méi)有這么好。如果所有的數(shù)字都落在同一個(gè)桶中，那就退化成一般的排序了。
前面說(shuō)的幾大排序算法 ，大部分時(shí)間復(fù)雜度都是O（n2），也有部分排序算法時(shí)間復(fù)雜度是O(nlogn)。而桶式排序卻能實(shí)現(xiàn)O（n）的時(shí)間復(fù)雜度。但桶排序的缺點(diǎn)是：
1）首先是空間復(fù)雜度比較高，需要的額外開(kāi)銷大。排序有兩個(gè)數(shù)組的空間開(kāi)銷，一個(gè)存放待排序數(shù)組，一個(gè)就是所謂的桶，比如待排序值是從0到m-1，那就需要m個(gè)桶，這個(gè)桶數(shù)組就要至少m個(gè)空間。
2）其次待排序的元素都要在一定的范圍內(nèi)等等。
桶式排序是一種分配排序。分配排序的特定是不需要進(jìn)行關(guān)鍵碼的比較，但前提是要知道待排序列的一些具體情況。
總結(jié)
