1 快速排序（QuickSort）
快速排序是一個(gè)就地排序，分而治之，大規(guī)模遞歸的算法。從本質(zhì)上來說，它是歸并排序的就地版本。快速排序可以由下面四步組成。
（1） 如果不多于1個(gè)數(shù)據(jù)，直接返回。
（2） 一般選擇序列最左邊的值作為支點(diǎn)數(shù)據(jù)。
（3） 將序列分成2部分，一部分都大于支點(diǎn)數(shù)據(jù)，另外一部分都小于支點(diǎn)數(shù)據(jù)。
（4） 對(duì)兩邊利用遞歸排序數(shù)列。
快速排序比大部分排序算法都要快。盡管我們可以在某些特殊的情況下寫出比快速排序快的算法，但是就通常情況而言，沒有比它更快的了。快速排序是遞歸的，對(duì)于內(nèi)存非常有限的機(jī)器來說，它不是一個(gè)好的選擇。
2 歸并排序（MergeSort）
歸并排序先分解要排序的序列，從1分成2，2分成4，依次分解，當(dāng)分解到只有1個(gè)一組的時(shí)候，就可以排序這些分組，然后依次合并回原來的序列中，這樣就可以排序所有數(shù)據(jù)。合并排序比堆排序稍微快一點(diǎn)，但是需要比堆排序多一倍的內(nèi)存空間，因?yàn)樗枰粋€(gè)額外的數(shù)組。
3 堆排序（HeapSort）
堆排序適合于數(shù)據(jù)量非常大的場(chǎng)合（百萬數(shù)據(jù)）。
堆排序不需要大量的遞歸或者多維的暫存數(shù)組。這對(duì)于數(shù)據(jù)量非常巨大的序列是合適的。比如超過數(shù)百萬條記錄，因?yàn)榭焖倥判颍瑲w并排序都使用遞歸來設(shè)計(jì)算法，在數(shù)據(jù)量非常大的時(shí)候，可能會(huì)發(fā)生堆棧溢出錯(cuò)誤。
堆排序會(huì)將所有的數(shù)據(jù)建成一個(gè)堆，最大的數(shù)據(jù)在堆頂，然后將堆頂數(shù)據(jù)和序列的最后一個(gè)數(shù)據(jù)交換。接下來再次重建堆，交換數(shù)據(jù)，依次下去，就可以排序所有的數(shù)據(jù)。
4 Shell排序（ShellSort）
Shell排序通過將數(shù)據(jù)分成不同的組，先對(duì)每一組進(jìn)行排序，然后再對(duì)所有的元素進(jìn)行一次插入排序，以減少數(shù)據(jù)交換和移動(dòng)的次數(shù)。平均效率是O(nlogn)。其中分組的合理性會(huì)對(duì)算法產(chǎn)生重要的影響。現(xiàn)在多用D.E.Knuth的分組方法。
Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相對(duì)比較簡(jiǎn)單，它適合于數(shù)據(jù)量在5000以下并且速度并不是特別重要的場(chǎng)合。它對(duì)于數(shù)據(jù)量較小的數(shù)列重復(fù)排序是非常好的。
5 插入排序（InsertSort）
插入排序通過把序列中的值插入一個(gè)已經(jīng)排序好的序列中，直到該序列的結(jié)束。插入排序是對(duì)冒泡排序的改進(jìn)。它比冒泡排序快2倍。一般不用在數(shù)據(jù)大于1000的場(chǎng)合下使用插入排序，或者重復(fù)排序超過200數(shù)據(jù)項(xiàng)的序列。
6 冒泡排序（BubbleSort）
冒泡排序是最慢的排序算法。在實(shí)際運(yùn)用中它是效率最低的算法。它通過一趟又一趟地比較數(shù)組中的每一個(gè)元素，使較大的數(shù)據(jù)下沉，較小的數(shù)據(jù)上升。它是O(n^2)的算法。
7 交換排序（ExchangeSort）和選擇排序（SelectSort）
這兩種排序方法都是交換方法的排序算法，效率都是 O(n2)。在實(shí)際應(yīng)用中處于和冒泡排序基本相同的地位。它們只是排序算法發(fā)展的初級(jí)階段，在實(shí)際中使用較少。
8 基數(shù)排序（RadixSort）
基數(shù)排序和通常的排序算法并不走同樣的路線。它是一種比較新穎的算法，但是它只能用于整數(shù)的排序，如果我們要把同樣的辦法運(yùn)用到浮點(diǎn)數(shù)上，我們必須了解浮點(diǎn)數(shù)的存儲(chǔ)格式，并通過特殊的方式將浮點(diǎn)數(shù)映射到整數(shù)上，然后再映射回去，這是非常麻煩的事情，因此，它的使用同樣也不多。而且，最重要的是，這樣算法也需要較多的存儲(chǔ)空間。
9 總結(jié)
下面是一個(gè)總的表格，大致總結(jié)了我們常見的所有的排序算法的特點(diǎn)。
| 排序法 |
平均時(shí)間 |
最差情形 |
穩(wěn)定度 |
額外空間 |
備注 |
| 冒泡 |
O(n2) |
O(n2) |
穩(wěn)定 |
O(1) |
n小時(shí)較好 |
| 交換 |
O(n2) |
O(n2) |
不穩(wěn)定 |
O(1) |
n小時(shí)較好 |
| 選擇 |
O(n2) |
O(n2) |
不穩(wěn)定 |
O(1) |
n小時(shí)較好 |
| 插入 |
O(n2) |
O(n2) |
穩(wěn)定 |
O(1) |
大部分已排序時(shí)較好 |
| 基數(shù) |
O(logRB) |
O(logRB) |
穩(wěn)定 |
O(n) |
B是真數(shù)(0-9)，
R是基數(shù)(個(gè)十百)
|
| Shell |
O(nlogn) |
O(ns) 1<2 |
不穩(wěn)定 |
O(1) |
s是所選分組 |
| 快速 |
O(nlogn) |
O(n2) |
不穩(wěn)定 |
O(nlogn) |
n大時(shí)較好 |
| 歸并 |
O(nlogn) |
O(nlogn) |
穩(wěn)定 |
O(1) |
n大時(shí)較好 |
| 堆 |
O(nlogn) |
O(nlogn) |
不穩(wěn)定 |
O(1) |
n大時(shí)較好 |