🌟個人博客：www.hellocode.top
🏰Java知識導航：Java-Navigate
🔥CSDN：HelloCode.
🌞知乎：HelloCode
🌴掘金：HelloCode
?如有問題，歡迎指正，一起學習~~
希爾排序是一種插入排序的改進版本，旨在解決插入排序在處理大規模數據時的效率問題。通過將數組分為多個子序列并對這些子序列進行局部排序，希爾排序逐步將元素“分組”并逐漸接近它們的最終排序位置。這種逐步的排序方式可以有效減少逆序對的數量，從而加快整體排序過程。
基本思想
這里使用五分鐘學算法大佬的動圖，很清晰
- 希爾排序將數組分成若干個子序列，每個子序列包含間隔為 h 的元素，稱為 h-子序列。
- 對每個 h-子序列應用插入排序，以實現局部排序。
- 不斷縮小 h 的值，重復步驟 2，直到 h 為 1。此時，整個序列基本有序，只需對相鄰元素進行插入排序即可。
一般間隔也就是gap的選取就是數組長度的一半，如上圖所示，原始數組為
[8,9,1,7,2,3,5,4,6,0]，初始間隔就是5，也就是會將圖中數組分為[8,3]、[9,5]、[1,4]、[7,6]、[2,0]共5組，然后對這些組合進行插入排序，并不斷縮小gap（每次縮小一半），重復進行插入排序操作，最終就能夠得到有序數組~
對分組不太理解的可以看下圖，非常清晰：
代碼實現
代碼的話還是循環，只需要在插入排序外層再加一層循環控制gap 的縮小即可，就是改良版的插入排序（需要對比圖片和插入排序的思路仔細體會），具體代碼如下：
/*** @author HelloCode* @blog https://www.hellocode.top* @date 2023年08月10日 20:59*/
public class ShellSort {public static void main(String[] args) {int[] arr = {8,9,1,7,2,3,5,4,6,0};System.out.println("原數組：" + Arrays.toString(arr));shellSort(arr);System.out.println("排序后：" + Arrays.toString(arr));}public static void shellSort(int[] arr){int n = arr.length;// 兩層for循環，外層不斷縮小gap(每次縮小為一半)for(int gap = n / 2; gap > 0; gap /= 2){// 內層對每組進行插入排序// 這里的i還是指向第一個待插入元素(也就是gap，可以看圖理解)// 此時已排序數組的最后一個元素，就應該是i - gap// 這里i的跨度就不應該是++而是 += gap（配合圖更好理解）for(int i = gap;i < n; i ++){int current = arr[i]; // 當前待插入元素int pre = i - gap; // 有序部分的最后一個元素下標// 當 i 位置元素大于等于 pre 位置元素時說明已經有序，就繼續i+= gapwhile(pre >= 0){// 已經是正確位置，直接退出循環if(current >= arr[pre]){break;}// 位置不正確，需要尋找正確位置arr[pre + gap] = arr[pre];pre -= gap;}//此時pre下標的值是負數了，將current的值放到pre變量加上一個gap的位置上arr[pre + gap] = current;}}}
}
測試：
原數組：[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
排序后：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
優化
- 希爾排序的性能高度依賴于步長序列的選擇。選擇不同的步長序列可能會對排序效率產生影響。
- 一些常見的步長序列包括希爾步長序列（h = n/2, n/4, n/8, …）、Sedgewick步長序列等。
- 通過嘗試不同的步長序列，可以選擇合適的步長來優化希爾排序的性能。
總結
優點
- 相對于傳統的插入排序，希爾排序通過將元素分組進行排序，減少了逆序對的數量，從而加快了排序過程。
- 希爾排序是原地排序算法，只需在原始數組上進行元素的交換和移動，不需要額外的輔助空間。
缺點
- 希爾排序的最壞情況時間復雜度并不穩定，通常在 O(n^2) 到 O(n log n) 之間。雖然平均情況下性能較好，但在某些特定情況下，性能可能不如其他高級排序算法。
- 步長序列的選擇對性能產生影響，選擇不當可能導致排序效率下降。
復雜度
- 時間復雜度：取決于步長序列的選擇，通常在 O(n log n) 到 O(n^2) 之間。
- 空間復雜度：原地排序，空間復雜度為 O(1)。
使用場景
- 希爾排序適用于中等規模的數據集，對于大規模數據，其性能可能不如其他更高級的排序算法。
- 在實際應用中，希爾排序的性能可能會比預期的好，尤其在某些特定情況下，例如對部分有序的數據進行排序時。
當使用希爾排序時，應特別注意其時間和空間復雜度的說明是基于最壞情況下的估計。這樣的估計可能會高于實際情況。希爾排序在某些實際應用中可能表現得比預期的要好。
)
