前言
直接插入排序當(dāng)待排序數(shù)據(jù)的順序和期望排序結(jié)果相反時(shí)，排序效率是最差的引谜；上次聊到的折半插入排序只是減少有序列表的比較次數(shù)牍陌，而對(duì)于整體數(shù)據(jù)遍歷次數(shù)還是沒有得到優(yōu)化；接下來(lái)要說(shuō)的希爾排序就是針對(duì)整體數(shù)據(jù)進(jìn)行優(yōu)化员咽，從而提升排序效率毒涧。
正文
1.1 希爾排序算法思想
希爾排序(Shell's Sort)是直接插入排序算法的改進(jìn)版，又稱“縮小增量排序”（Diminishing Increment Sort）;
算法思想
將待排序數(shù)據(jù)根據(jù)指定步長(zhǎng)進(jìn)行分組贝室，分別進(jìn)行直接插入排序契讲；減小步長(zhǎng)，重復(fù)分組滑频，重復(fù)直接插入排序捡偏，直到步長(zhǎng)為1時(shí)進(jìn)行最后一次插入排序。
對(duì)于第一次步長(zhǎng)可以根據(jù)需要自定義峡迷，但一般推薦會(huì)設(shè)置為元素個(gè)數(shù)除以2(lenght/2)银伟，后續(xù)的步長(zhǎng)依次是上一次步長(zhǎng)除以2(stepk=stepk-1/2)，直到步長(zhǎng)為1绘搞，如下圖：
上面說(shuō)到步長(zhǎng)可以理解為增量彤避，而減少步長(zhǎng)的過(guò)程，也就是縮小增量夯辖，即希爾排序又稱為縮小增量排序忠藤。
分組原理(第一次分組的step1=6/2=3)：
第一組：0索引位的元素為2，0+step1的索引位為3楼雹，對(duì)應(yīng)的元素是1模孩，3+step1越界了，則第一組的元素為2贮缅、1榨咐；
第二組：1索引位的元素為5，1+step1的索引位為4谴供，對(duì)應(yīng)的元素是9块茁，4+step1越界了，則第二組的元素為5桂肌、9数焊；
第三組：2索引位的元素為6，2+step1的索引位為5崎场，對(duì)應(yīng)的元素是3佩耳，5+step1越界了，則第三組的元素為6谭跨、3干厚；此時(shí)元素就分組完成了李滴；
接下來(lái)的分組就依次遞減步長(zhǎng)，即上一次步長(zhǎng)除以2取整蛮瞄； 然后根據(jù)新算出來(lái)的步長(zhǎng)繼續(xù)將上一次的排序的結(jié)果分組即可所坯；直到步長(zhǎng)遞減到為1時(shí)，整體進(jìn)行最后一次直接插入排序?yàn)橹梗?/p>
1.2 希爾排序算法實(shí)現(xiàn)與解析
代碼實(shí)現(xiàn)(升序)：
運(yùn)行結(jié)果如下：
步驟解析：
上圖步驟說(shuō)明：
將原始數(shù)據(jù)array復(fù)制到新數(shù)組中arrayb中挂捅，這步的主要目的是后續(xù)不需要聲明額外臨時(shí)變量芹助，也為了后續(xù)核心代碼實(shí)現(xiàn)邏輯簡(jiǎn)單易懂，減少過(guò)多的判斷闲先；0索引位也充當(dāng)為哨兵位状土；
第一步根據(jù)元素個(gè)數(shù)算出第一次步長(zhǎng)step1=3，根據(jù)步長(zhǎng)將待排序數(shù)據(jù)進(jìn)行虛擬分組饵蒂，索引位為1的元素和索引位為1+step的元素為一組声诸，索引位為2的元素和索引位為2+step的元素為一組酱讶，索引位為3的元素和索引位為3+step的元素為一組退盯；則將待排序數(shù)據(jù)分為2、1泻肯；5渊迁、9；6灶挟、3 三組琉朽；
第二步開始遍歷每一組數(shù)據(jù)，針對(duì)每一組數(shù)據(jù)進(jìn)行直接插入排序稚铣； 首先是第一組數(shù)據(jù)2箱叁、1，將待排序數(shù)據(jù)1放入哨兵位(即0索引位)惕医，哨兵位的數(shù)據(jù)1和有序列表中的2進(jìn)行比較耕漱，2大于1，則需要騰出空位抬伺，所以2移到分組中索引位為4的位置螟够；然后將哨兵位的數(shù)據(jù)1插入到騰出的空位中；
第三步遍歷第二組數(shù)據(jù)5峡钓、9妓笙，首先將待排序數(shù)據(jù)9放入哨兵位(即0索引位)，哨兵位的數(shù)據(jù)9和有序列表中的5進(jìn)行比較能岩，5小于9寞宫，則不需改變位置；
第四步遍歷第三組數(shù)據(jù)6拉鹃、3淆九，首先將待排序數(shù)據(jù)3放入哨兵位(即0索引位)统锤，哨兵位的數(shù)據(jù)3和有序列表中的6進(jìn)行比較，6大于3炭庙，則需要騰出空位饲窿，所以6移到分組中索引位為6的位置；然后將哨兵位的數(shù)據(jù)3插入到騰出的空位中焕蹄；
-
分組排序完成之后逾雄，最終得出第一次分組排序結(jié)果：image
第一次分組排序完成之后，調(diào)整步長(zhǎng)腻脏，繼續(xù)進(jìn)行分組鸦泳，由于第二次計(jì)算出的步長(zhǎng)step2=step1/2=1，即將所有上一次分組的數(shù)據(jù)全部為一組進(jìn)行最后一次直接插入排序即可永品；這里就不在重復(fù)演示了做鹰，具體步驟和之前說(shuō)到的直接插入排序一樣，參照這篇大牛領(lǐng)導(dǎo)單獨(dú)找我聊了兩句：搞框架的同時(shí)別忘了算法鼎姐。
通過(guò)第二次插入排序完成之后就得到最后的排序結(jié)果啦钾麸。
1.3 希爾排序算法分析
時(shí)間復(fù)雜度
時(shí)間復(fù)雜度最壞情況和直接插入排序的時(shí)間復(fù)雜一樣，都是O(n2)炕桨，但有其他大神經(jīng)過(guò)大量演示饭尝，希爾排序的時(shí)間復(fù)雜度一般為O(n(1.3~2))，比O(n2)性能好献宫。
空間復(fù)雜度 在算法核心部分只采用了固定的幾個(gè)中間變量((i,j,step,arrayb[0]))钥平，所以算法過(guò)程中消耗的內(nèi)存是一個(gè)常量，則空間復(fù)雜度為O(1)姊途；
穩(wěn)定性 由于在排序過(guò)程中是根據(jù)步長(zhǎng)將原始數(shù)據(jù)進(jìn)行分組涉瘾，這樣就可能會(huì)導(dǎo)致相同的元素分到不同組，在最終排序時(shí)就不能保證原來(lái)兩個(gè)相同元素的順序啦捷兰，所以希爾排序是不穩(wěn)定的立叛。
綜上所述，希爾排序的時(shí)間復(fù)雜度為O(n2)寂殉，空間復(fù)雜度為O(1)囚巴，是不穩(wěn)定算法；
總結(jié)
到這里友扰，插入排序的三種排序介紹完畢彤叉，下期開始介紹交換排序；這里先總結(jié)一下插入排序的相關(guān)關(guān)鍵點(diǎn)(下圖綠色部分)村怪；如下：
感謝小伙伴的：點(diǎn)贊秽浇、收藏和評(píng)論，下期繼續(xù)~~~
一個(gè)被程序搞丑的帥小伙甚负，關(guān)注"Code綜藝圈"柬焕，跟我一起學(xué)~~~
