總算進(jìn)入我們的排序相關(guān)算法的學(xué)習(xí)了。相信不管是系統(tǒng)學(xué)習(xí)過的還是沒有系統(tǒng)學(xué)習(xí)過算法的朋友都會(huì)聽說過許多非常出名的排序算法，當(dāng)然，我們今天入門的內(nèi)容并不是直接先從最常見的那個(gè)算法說起，而是按照一定的規(guī)則一個(gè)一個(gè)的介紹。
首先，我們要介紹的排序算法是插入類型的排序算法。顧名思義，插入排序就是將無序的一個(gè)或幾個(gè)記錄“插入”到有序的序列中，比較典型的例子就是簡(jiǎn)單插入排序和希爾排序。
簡(jiǎn)單插入排序，也可以叫做直接插入排序。還是先看代碼，再來進(jìn)行下一步的解釋。
function InsertSort($arr)
{
$n = count($arr);
for ($i = 1; $i < $n; $i++) { // 開始循環(huán)，從第二個(gè)元素開始，下標(biāo)為 1 的
$tmp = $arr[$i]; // 取出未排序序列第一個(gè)元素
for ($j = $i; $j > 0 && $arr[$j - 1] > $tmp; $j--) { // 判斷從當(dāng)前下標(biāo)開始向前判斷，如果前一個(gè)比當(dāng)前元素大
$arr[$j] = $arr[$j - 1]; // 依次移動(dòng)元素
}
// 將元素放到合適的位置
$arr[$j] = $tmp;
}
echo implode(', ', $arr), PHP_EOL;
}
InsertSort($numbers);
// 49, 38, 65, 97, 76, 13, 27, 49
// 13, 27, 38, 49, 49, 65, 76, 97
代碼量不多吧，其實(shí)也非常好理解。我們就拿測(cè)試數(shù)據(jù)的前兩個(gè)數(shù)來簡(jiǎn)單地說明一下。
首先，第一個(gè)循環(huán)是從 1 開始的，也就是說，第一個(gè)取出的未排序序列元素是 tmp = arr[1] ，也就是當(dāng)前的 tmp = 38 。
然后開始循環(huán)，當(dāng)前的循環(huán)是判斷 j-1 的元素是否比當(dāng)前這個(gè) tmp 元素大，如果是的話，進(jìn)入循環(huán)體，arr[1] = arr[0] 。到目前為止，arr[0] 和 arr[1] 現(xiàn)在都是 49 。整個(gè)序列是 49,49,65,……
最后讓 arr[0] = $tmp ，也就是等于 38 。（循環(huán)的時(shí)候 j-- 了）。整個(gè)序列是 38,49,65,……
通過下面這張圖片，我們可以更清楚地看明白整個(gè)序列完成排序的過程。
從上面的步驟可以看出，簡(jiǎn)單插入排序就是從一邊開始，先讓前面的數(shù)據(jù)逐步有序的過程。從代碼中就可以看出，它是不斷地內(nèi)部地循環(huán)中進(jìn)行 j 的遞減，與前面有序的數(shù)列進(jìn)行比對(duì)，當(dāng)發(fā)現(xiàn)了自己合適的位置之后，就將數(shù)據(jù)放到這個(gè)位置上。
從代碼和我們的分析來看，簡(jiǎn)單插入排序的時(shí)間復(fù)雜度是 O(n2) 。同時(shí)，它是屬于穩(wěn)定的排序，什么叫穩(wěn)定排序呢？細(xì)心的同學(xué)應(yīng)該發(fā)現(xiàn)了，在我們的測(cè)試代碼中，有兩個(gè)相同的數(shù)據(jù)，也就是 49 。穩(wěn)定的意思就是相同的數(shù)據(jù)在排序前后的位置不會(huì)發(fā)生改變，前面的 49 依然是在后面的 49 前面。這就是排序的穩(wěn)定性。
另外，簡(jiǎn)單插入排序比較適合初始記錄基本有序的情況，當(dāng)初始記錄無序，n 較大時(shí)，這個(gè)算法的時(shí)間復(fù)雜度會(huì)比較高，不太適合采用。
簡(jiǎn)單插入排序很好理解吧，希爾排序又是什么鬼呢？別著急，從這個(gè)名字我們是看不出什么端倪的，因?yàn)檫@個(gè)排序的名字是以它的發(fā)現(xiàn)者命名的。實(shí)際上，希爾排序還是一個(gè)插入排序的算法。
上文中說過，簡(jiǎn)單插入排序適合基本有序的情況，而希爾排序就是為了提升簡(jiǎn)單插入排序的效率而出現(xiàn)的，它主要目的是減少排序的 n 的大小以及通過幾次排序就讓數(shù)據(jù)形成基本有序的格式。
對(duì)于這個(gè)算法，我們不能先上代碼了，先來看圖吧。
看明白了嗎？我們其實(shí)是將數(shù)據(jù)進(jìn)行分組了，每次分組是以一定的增量為基礎(chǔ)的，比如我們這個(gè)示意圖中就是第一次以 5 為增量進(jìn)行排序，第二次是以 3 為增量。這樣第三次排序的時(shí)候，增量為 1 ，也就成為一個(gè)普通的簡(jiǎn)單插入排序了。一會(huì)我們代碼中就會(huì)體現(xiàn)出來。
還是按增量為迭代次序進(jìn)行這三趟排序的具體分析吧：
1）第一次迭代的時(shí)候，我們將分組增量設(shè)置為 5 ，這時(shí)分別有三組數(shù)據(jù)，也就是 49 和 13，38 和 27，65 和 49 ，然后對(duì)這三組數(shù)據(jù)進(jìn)行簡(jiǎn)單插入排序，之后的數(shù)組結(jié)果是 13、27、49、97、76、49、38、65 。
2）第二次迭代，分組增量為 3，這時(shí)就分成了兩組，每組三個(gè)數(shù)據(jù)，分別是 13、97、38 為一組，另一組是 27 、76 、65 。對(duì)這兩組數(shù)據(jù)進(jìn)行簡(jiǎn)單插入排序之后更新數(shù)組結(jié)果為 13、27、49、38、65、49、97、76 。
3）其實(shí)從兩次分組排序之后就可以看出，這個(gè)數(shù)組已經(jīng)基本有序了。這時(shí)最后就是以分組增量 1 再次進(jìn)行簡(jiǎn)單插入排序。說白了，最后這一步就是一個(gè)普通的簡(jiǎn)單插入排序的過程了。
分步驟講解之后是不是清楚很多了，再重復(fù)一篇，希爾排序其實(shí)就是按分組來一次大范圍的插入排序，最后一步步縮小到只有 1 次增量的簡(jiǎn)單插入排序了。我們?cè)賮砜纯创a吧：
function ShellSort($arr)
{
$n = count($arr);
$sedgewick = [5, 3, 1];
// 初始的增量值不能超過待排序列的長(zhǎng)度
for ($si = 0; $sedgewick[$si] >= $n; $si++);
// 開始分組循環(huán)，依次按照 5 、3 、 1 進(jìn)行分組
for ($d = $sedgewick[$si]; $d > 0; $d = $sedgewick[++$si]) {
// 獲取當(dāng)前的分組數(shù)量
for ($p = $d; $p < $n; $p++) {
$tmp = $arr[$p];
// 插入排序開始，在當(dāng)前組內(nèi)
for ($i = $p; $i >= $d && $arr[$i - $d] > $tmp; $i -= $d) {
$arr[$i] = $arr[$i - $d];
}
$arr[$i] = $tmp;
}
}
echo implode(', ', $arr), PHP_EOL;
}
ShellSort($numbers);
看著代碼貌似有三層 for 循環(huán)呀，它哪里提升了效率了呢？其實(shí)希爾排序的效率提升確實(shí)是有限的，它其實(shí)是通過前幾次的分組讓數(shù)據(jù)先基本有序。而在分組的狀態(tài)中，數(shù)據(jù)比較的數(shù)量并不會(huì)達(dá)到 n 的級(jí)別。當(dāng)最后一次進(jìn)行簡(jiǎn)單排序的時(shí)候，整個(gè)數(shù)據(jù)已經(jīng)是基本有序了，在這種情況下交換的次數(shù)明顯也會(huì)減少很多，所以它的時(shí)間復(fù)雜度在理想狀態(tài)下可以減少到 O(log2n)2 的水平。
排序的入門餐怎么樣？我們可不是直接就拿爛大街的冒泡和快排上手的吧。不出名不意味著不會(huì)用到，比如我面試的時(shí)候曾經(jīng)有個(gè)公司就是在面試題上寫明了不能使用冒泡和快排。這時(shí)候，我相信簡(jiǎn)單插入排序直觀好理解的特性一定就能幫助我們度過這種面試難關(guān)了哦！
測(cè)試代碼：
https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/7.排序/source/7.1插入類排序：簡(jiǎn)單插入、希爾排序.php
參考文檔：
本文示例選自 《數(shù)據(jù)結(jié)構(gòu)》第二版，嚴(yán)蔚敏
《數(shù)據(jù)結(jié)構(gòu)》第二版，陳越
聯(lián)系客服
