大豐城鄉(xiāng)建設(shè)局網(wǎng)站中文域名注冊(cè)管理中心
希爾排序（ShellSort）是以它的發(fā)明者Donald Shell名字命名的，希爾排序是插入排序的改進(jìn)版，實(shí)現(xiàn)簡(jiǎn)單，對(duì)于中等規(guī)模數(shù)據(jù)的性能表現(xiàn)還不錯(cuò)
一、排序思想
前情回顧：漫畫：什么是插入排序算法？（對(duì)插入排序不熟悉的強(qiáng)烈建議先閱讀此文）
一天，一塵拿著撲克自己在那玩，剛被師傅看見了
數(shù)據(jù)有序程度越高，越高效（移動(dòng)少）
首先它把較大的數(shù)據(jù)集合分割成若干個(gè)小組（邏輯上分組），然后對(duì)每一個(gè)小組分別進(jìn)行插入排序，此時(shí)，插入排序所作用的數(shù)據(jù)量比較小（每一個(gè)小組），插入的效率比較高
**注意：**下面有顏色的是邏輯上的分組，并沒有實(shí)際地進(jìn)行分組操作，在數(shù)組中的位置還是原來的樣子，只是將他們看成這么幾個(gè)分組（邏輯上分組）
可以看出，他是按下標(biāo)相隔距離為4分的組，也就是說把下標(biāo)相差4的分到一組，比如這個(gè)例子中a[0]與a[4]是一組、a[1]與a[5]是一組…，這里的差值（距離）被稱為增量
每個(gè)分組進(jìn)行插入排序后，各個(gè)分組就變成了有序的了（整體不一定有序）
此時(shí)，整個(gè)數(shù)組變的部分有序了（有序程度可能不是很高）
然后縮小增量為上個(gè)增量的一半:2，繼續(xù)劃分分組，此時(shí)，每個(gè)分組元素個(gè)數(shù)多了，但是，數(shù)組變的部分有序了，插入排序效率同樣比較高
同理對(duì)每個(gè)分組進(jìn)行排序（插入排序），使其每個(gè)分組各自有序
最后設(shè)置增量為上一個(gè)增量的一半：1，則整個(gè)數(shù)組被分為一組，此時(shí)，整個(gè)數(shù)組已經(jīng)接近有序了，插入排序效率高
同理，對(duì)這僅有的一組數(shù)據(jù)進(jìn)行排序，排序完成
二、排序代碼
對(duì)于已經(jīng)熟悉插入排序的一塵來說這并不是什么難事，很快，一塵寫出了希爾排序的代碼
隨后一塵寫出了插入arr[i]到所在組正確位置的代碼（insertI）
insertI 和直接插入排序里的插入代碼幾乎完全一樣
三、時(shí)間復(fù)雜度
接下來又是分析時(shí)間復(fù)雜度吧，一塵心里想
希爾排序的復(fù)雜度和增量序列是相關(guān)的
{1,2,4,8,…}這種序列并不是很好的增量序列，使用這個(gè)增量序列的時(shí)間復(fù)雜度（最壞情形）是O(n^2)
Hibbard提出了另一個(gè)增量序列{1,3,7，…,2k-1}，這種序列的時(shí)間復(fù)雜度(最壞情形)為O(n1.5)
Sedgewick提出了幾種增量序列，其最壞情形運(yùn)行時(shí)間為O（n^1.3）,其中最好的一個(gè)序列是{1,5,19,41,109,…}
對(duì)不同增量的復(fù)雜度感性趣可以參考《數(shù)據(jù)結(jié)構(gòu)與算法分析》一書或其他相關(guān)論文
四、穩(wěn)定性
關(guān)于穩(wěn)定性可看：冒泡排序
說完，一塵繼續(xù)玩起了撲克
更多排序算法文章
1. 漫畫：什么是冒泡排序算法？
2. 漫畫：什么是選擇排序算法？
3. 漫畫：什么是插入排序算法？
4. 漫畫：什么是希爾排序算法？
5. 漫畫：什么是歸并排序算法？
6. 漫畫：什么是快速排序算法？
7. 漫畫：什么是堆排序算法？
8. 漫畫：什么是基數(shù)排序算法？
9. 漫畫：什么是外部排序？
10. 什么是計(jì)數(shù)排序？
11. 十大排序算法極簡(jiǎn)匯總篇
推薦閱讀
下載破 2w+，在校生必看，《程序員內(nèi)功修煉》第二版出爐
從雙非到大廠，帥地寫了一本原創(chuàng)PDF送給大家
一個(gè)幫你拿offer的校招網(wǎng)站
算法刷題路線(系統(tǒng)+全面)
作者簡(jiǎn)介：我是帥地，校招拿到過不少大廠offer，畢業(yè)去了騰訊研發(fā)崗，畢業(yè)半年整到人生第一個(gè) 100 萬，目前專注于寫大學(xué)規(guī)劃 + 校招求職相關(guān)的內(nèi)容，著有個(gè)人原創(chuàng)網(wǎng)站 PlayOffer。