根據(jù)將排序記錄是否全部放置在內(nèi)存中，將排序分為內(nèi)排序和外排序，之前講的都是內(nèi)排序，這里總結(jié)一下，內(nèi)排序分為四類(lèi)：插入排序、交換排序、選擇排序和歸并排序。前幾篇介紹的7種算法分別是各種分類(lèi)的代表算法：
目前還沒(méi)有十全十美的排序算法，即使是快速排序法，也只是在整體性能上優(yōu)越，它也存在排序不穩(wěn)定、需要大量輔助空間、對(duì)少量數(shù)據(jù)排序無(wú)優(yōu)勢(shì)等不足。這里我們就來(lái)從多個(gè)角度來(lái)剖析一下提到的各種排序的長(zhǎng)與短。
我們將7種算法的各種指標(biāo)進(jìn)行對(duì)比：
從算法的簡(jiǎn)單性來(lái)看，分為兩類(lèi)：
- 簡(jiǎn)單算法：冒泡、選擇、插入。
- 改進(jìn)算法：希爾、堆、歸并、快速。
平均情況： 顯然最后3種改進(jìn)算法要?jiǎng)龠^(guò)希爾排序，并遠(yuǎn)遠(yuǎn)勝超過(guò)前3種簡(jiǎn)單算法，所以堆、歸并、快速算法要好一點(diǎn)。
最好情況：冒泡和插入排序要更勝一籌，如果你的待排序序列總是基本有序，你就考慮這兩種算法。
最壞情況：堆排序和歸并排序又強(qiáng)于快速排序以及其他簡(jiǎn)單排序。
空間復(fù)雜度： 歸并排序和快速排序就比較消耗內(nèi)存。所以不要選擇歸并排序和快速排序。
穩(wěn)定性： 歸并排序 獨(dú)占鰲頭。
待排序記錄的個(gè)數(shù)： 待排序的個(gè)數(shù)n越少，采用簡(jiǎn)單排序方法越合適，反之，n越大，采用改進(jìn)排序方法越合適。至于n多少比較合適，目前還沒(méi)有定義。
從表中看，似乎選擇排序在3種簡(jiǎn)單排序中性能最差，其實(shí)也不完全是，比如，如果比較的關(guān)鍵字信息量比大，比較次數(shù)比較多，這樣移動(dòng)記錄所花費(fèi)的時(shí)間也就越多，我們給出3種簡(jiǎn)單排序算法的移動(dòng)次數(shù)比較：
總之，從指標(biāo)來(lái)看，快速排序是性能最好的排序算法，如果求穩(wěn)定的話，建議選擇歸并排序。
