前言

已發(fā)布：

【算法知識】詳解選擇冒泡算法

【算法知識】詳解選擇排序算法

【算法知識】詳解插入排序算法

當待插入元素是一個很小(當需求是從小到大排序時，從大到小排序時此處為很大)直接插入排序需要移動較多次數(shù)，性能會很差。希爾排序解決了這一問題。

基本思想

希爾排序的基本思想：把序列按下標的一定增量分組，對每組使用直接插入排序算法排序；
隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。
如果對直接插入排序不了解的朋友，可以看我的這篇文章：
詳解直接插入排序算法

例子

給定數(shù)組arr為 [ 3 , 6 , 5 , 12 , 1 , 75 , 10 ， -3， 0 ] 初始狀態(tài)見下圖：

初始序列

定義變量 h為增量，初始值為5 。

第一輪根據(jù)增量設置成5組，顏色相同的為一組。

對每一組進行直接插入排序得到：

然后 h減半向下取整；
則 h = 3；

第二輪根據(jù)增量設置成5組，顏色相同的為一組。

對每一組進行直接插入排序得到：

第二輪進行插入排序

然后 h減半向下取整；
則 h = 1；

第三輪增量為1，所有序列為一組。

第三輪進行插入排序

插入排序后得到：

h此時為1，全部有序，完畢。

由例子可知，每次都可以達到組內部分有序，大大減少了插入排序的移動開銷。

代碼

首先說下步長的選擇：步長的選擇一般時這樣的：

int?h?=?1; while(h?<?arr.length?/?2){h?=?2?*?h?+?1; }

即先把步長設置為1，只要 h 小于數(shù)組長度一半（向下取整）就在原基礎上乘以2再加上1；
那么，本文的例子中的步長計算為：
初始設為1；
arr.length為9，其一半向下取整為4；
1 < 4；則 h 修正為 h = 1 * 2 + 1 = 3；
3 <4 仍成立，h修正為 h = 3 *2 + 1 = 7 。
本文一開始將 h 選為5，是為了演示方便。

根據(jù)步長分組后，進行插入排序的代碼為:

for(int?i=?h?;?i<?arr.length;i++){value?=?arr[i];index?=?i?-?h;//初始為前一個元素while(index?>=0?&&?value?<?arr[index]){//需要保證index合法//每當前面的元素比待插入元素大，就向后移動arr[index?+?h]?=?arr[index];//不用怕覆蓋，因為value保存著待插入的值index?-=?h;}//當退出循環(huán)，表明已經找到了待插入位置，即index?+?harr[index?+?h]?=?value;}

對外層循環(huán)進行解釋：i 的初始值為 h,即第一個待進行插入排序的元素的索引，?i - h即為本組待插入元素的最前面元素的索引。

i++表示下一組待插入元素的索引。

內層循環(huán)就是插入排序的代碼。
如果對直接插入排序不了解的朋友，可以看我的這篇文章：

詳解直接插入排序算法

其他

希爾排序的時間復雜度有很多種說法，證明也比較復雜，本文不過多討論。
關于穩(wěn)定性：
在不同的插入排序過程中，相等的元素可能在各自的插入排序中發(fā)生移動，最后其前后相對位置會發(fā)生改變，所以希爾排序是不穩(wěn)定的。

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習在線手冊深度學習在線手冊AI基礎下載（pdf更新到25集）本站qq群1003271085，加入微信群請回復“加群”獲取一折本站知識星球優(yōu)惠券，復制鏈接直接打開：https://t.zsxq.com/yFQV7am喜歡文章，點個在看

總結

以上是生活随笔為你收集整理的【算法知识】详解希尔排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。