圖解算法---希爾排序
前情回顧：直接插入排序（對(duì)插入排序不熟悉的建議先閱讀此文）
一天颁督，一塵拿著撲克自己在那玩爸舒，剛被師傅看見(jiàn)了
首先它把較大的數(shù)據(jù)集合分割成若干個(gè)小組（邏輯上分組），然后對(duì)每一個(gè)小組分別進(jìn)行插入排序壹若，此時(shí)嗅钻，插入排序所作用的數(shù)據(jù)量比較小（每一個(gè)小組）店展，插入的效率比較高
可以看出养篓，他是按下標(biāo)相隔距離為4分的組，也就是說(shuō)把下標(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)行排序，排序完成
隨后一塵寫(xiě)出了插入arr[i]到所在組正確位置的代碼（insertI）
希爾排序的復(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,...}
