1. 概念

希爾排序也是一種插入排序，它是簡單插入排序經過改進之后的一個更高效的版本，也稱為縮小增量排序。希爾排序在數組中采用跳躍式分組的策略，通過某個增量將數組元素劃分為若干組，然后分組進行插入排序，隨后逐步縮小增量，繼續按組進行插入排序操作，直至增量為1。

推薦一個B站六分鐘的視頻，PPT動畫做的非常好，清晰明了。

2. 思路

① 希爾排序采用跳躍式的分組方式，什么是跳躍式？也就是說同一組內的成員在原序列中實際上是互相隔著一段距離的，它們被迫抽出來組成一隊，內部采用插入排序比較大小。它們互相隔著的距離是相等的，這個距離我們稱它為增量，增量怎么確定？一般來說，初始增量值為序列長度的一半，接下來我們根據增量值計算分組，如下圖增量為5，所以索引0跟索引5一組，索引1跟索引6一組 …，以此類推，序列被分成了五組；

② 分了組之后，組員內部要進行插入排序的，但是這里的插入排序步長其實并不是1，我們知道原本的插入排序是從右往左一步一步地比較大小并插入的，但是希爾排序是跳躍式分組的，雖然說你們被分到了同一個隊伍里，但是不要忘記了，你們本身的索引并不相連，索引還是原來位置的索引，所以，在這里插入排序的時候，每一步的長度應該是增量的大小，除了步長不一樣外，其它思路都不變；

③ 在第一輪排序完成之后，發現整體上序列的順序有了一個大體的趨勢，小的基本在左邊，大的基本在右邊，但這才是第一步還不算排好序；

④ 再開始下一輪排序，每一輪開始時的增量值都應是上一輪增量值的一半。原理還不變，外部分組，內部插入排序，什么時候不再分組，不再排序？增量值一直減半，總有一天它會減為1，到1的時候就是全體序列進行最基本的插入排序了，沒錯這是最后一步，所以終止條件就是增量值開始小于1，這時候的序列已經完全有序。

3. 代碼實現

import java.util.Arrays;public class Test {public static void main(String[] args) {int[] arr = {2, 9, 3, 11, 7, 8, 4, 1, 6};int[] newArr = sort(arr);System.out.println(Arrays.toString(newArr));}public static int[] sort(int[] arr) {//控制增量值，初始值為序列長度的一半，每次減半，步長為0時停止for (int step = arr.length / 2; step > 0; step /= 2) {//控制待插入元素的位置，初始值為增量值for (int i = step; i < arr.length; i++) {//待插入元素int insertVal = arr[i];//待比較元素初始位置int index = i - step;//控制待比較元素的位置，初始值為待插入元素的位置減去增量值，即indexwhile (index >= 0 && insertVal < arr[index]) {//當前待比較元素向后移一位，這里的一位就是step長度arr[index + step] = arr[index];//指針向左挪動一位，繼續跟下一個元素作比較index -= step;}//退出循環后后，將待插入元素插入到index的下一位arr[index + step] = insertVal;}}return arr;}
}