思路
希爾排序，與其他排序不同的是工闺，別的排序都能通過名字關(guān)聯(lián)上，而希爾排序的名字瓣蛀，怎么看也不太像中文陆蟆。
其實希爾排序就是插入排序的進(jìn)化版，它會先聲明一個間隙參數(shù)惋增，然后按照間隙參數(shù)叠殷，把數(shù)組分成若干各子數(shù)組，對子數(shù)組進(jìn)行插入排序诈皿。隨著間隙越縮越小林束，整個數(shù)組的順序也就慢慢排好了。
看起來不太容易理解稽亏，下面就拆開說一下步驟：
- 計算出一個間隙值壶冒；
- 按照間隙值把數(shù)組分成若干個子數(shù)組；
- 對子數(shù)組進(jìn)行插入排序截歉；
- 將間隙縮小胖腾，重新分組并插入排序；
- 直至整個數(shù)組排序完成。
講解
有數(shù)組如下：
image.png
現(xiàn)在要對它進(jìn)行希爾排序咸作。首先計算出一個間隙值gap锨阿，我們用數(shù)組長度除以2，計算出第一個gap：8 / 2 = 4记罚；
那么間隔為4（比如下標(biāo)為0的元素群井，加4，即下標(biāo)為4的元素毫胜，兩個元素看做一個子數(shù)組）的元素即為一個子數(shù)組，我們用不同顏色將子數(shù)組標(biāo)記出來：
image.png
然后對子數(shù)組進(jìn)行插入排序诬辈，插入排序前面的文章講過了酵使，這里就直接進(jìn)行排序了：
image.png
然后將gap值自除2，計算出下一個gap為：4 / 2 = 2焙糟，并將數(shù)組重新拆分子數(shù)組：
image.png
這次就分成了兩個子數(shù)組口渔，繼續(xù)對這兩個子數(shù)組進(jìn)行排序：
image.png
順序越來越明顯了。gap再次自除2穿撮，計算出最后一個gap為：2 / 2 = 1缺脉，那么這次拆分出來的數(shù)組其實就是一個完整的數(shù)組了：
image.png
再次對數(shù)組進(jìn)行排序：
image.png
整個數(shù)組的順序就拍好啦，這就是希爾排序悦穿。
實現(xiàn)
@Test
public void shellSort() {
int[] nums = new int[]{26, -3, 14, -15, 0, 324, 1, 22};
sort(nums);
System.out.println(Arrays.toString(nums));
}
private void sort(int[] nums) {
// 如果數(shù)組長度小于2則不需要排序
if (nums.length < 2) {
return;
}
// 計算出第一個間隙值
int gap = nums.length / 2;
// 當(dāng)gap值自除到0時攻礼，說明已經(jīng)完成排序，結(jié)束遍歷
while (gap != 0) {
// 子數(shù)組個數(shù)栗柒，每個子數(shù)組都要排序礁扮，所以也是要遍歷的次數(shù)
for (int times = 0; times < nums.length / gap; times++) {
// 進(jìn)行插入排序，因為相鄰元素變成了間隙為gap瞬沦，所以單位都是gap
for (int i = times + gap; i < nums.length; i += gap) {
int cur = nums[i];
int insertIndex = -1;
for (int j = i - gap; j >= 0; j -= gap) {
if (nums[j] > cur) {
nums[j + gap] = nums[j];
insertIndex = j;
}
}
if (insertIndex != -1) {
nums[insertIndex] = cur;
}
}
}
// gap自除2
gap /= 2;
}
}
image.png
