目錄
1、希爾排序介紹
1.1、定義
1.2、核心思想
2、希爾排序的流程
第 1 輪：gap = 4
第 2 輪：gap = 2
第 3 輪：gap = 1
3、希爾排序的實現
4、時間復雜度分析
5、希爾排序的優缺點
6、適用場景
前言
????????希爾排序（Shell Sort）是一種基于插入排序的高效排序算法，由 Donald Shell 在 1959 年提出。
gap（間隔）是希爾排序的核心，它決定了如何將數組分成若干子序列進行插入排序。
-
初始?
gap?較大（如?n/2），逐步縮小，直到?gap = 1（此時就是普通插入排序）。 -
每次按?
gap?分組后，對每組進行獨立的插入排序。
gap的作用：
-
gap?的作用：-
控制分組的間隔，讓元素能“長距離跳躍”，減少后續操作次數。
-
-
子序列的劃分：
-
每隔?
gap?個元素取一個值，形成一組，組內進行插入排序。
-
-
為什么快？
-
大步長讓數據快速接近有序，小步長最終精細化調整。
-
1、希爾排序介紹
1.1、定義
????????它通過引入分組間隔（gap）來優化插入排序的性能，使得元素能夠更快地移動到正確的位置，從而減少比較和交換的次數。
1.2、核心思想
1、分組插入排序：
將整個數組按照一定的間隔（gap）分成若干子序列，對每個子序列進行插入排序。
2、逐步縮小間隔：
隨著排序的進行，gap 不斷縮小，直到 gap = 1（此時相當于普通的插入排序）。
3、最終排序：
當 gap = 1 時，數組已經基本有序，插入排序的效率會非常高（接近 O(n)）。
為什么比普通插入排序快？
? ? ? ? 插入排序在數據基本有序時效率很高（接近 O(n)），但在完全逆序時效率很低（O(n2)）。
????????希爾排序通過先讓數據“大致有序”，再執行插入排序，從而顯著提高性能。
2、希爾排序的流程
如下圖所示：
示例：
-
選擇一個 gap 序列（如?
n/2, n/4, ..., 1）。 -
對每個 gap 值，將數組分成若干子序列，并對每個子序列進行插入排序。
-
逐步縮小 gap，重復上述過程，直到 gap = 1 完成最終排序。
示例（gap = 4, 2, 1）：
原始數組：[8, 3, 6, 2, 1, 9, 5, 7, 4]假設數組為?[8, 3, 6, 2, 1, 9, 5, 7, 4]，長度為?n = 9。
我們以?Shell 原始序列（gap = n/2, n/4, ..., 1）為例：
第 1 輪：gap = 4
-
將數組按間隔 4 分組，即每隔 4 個元素取一個元素，形成子序列：
-
子序列 1：
arr[0],?arr[4],?arr[8]?→?[8, 1, 4] -
子序列 2：
arr[1],?arr[5]?→?[3, 9]（因為?arr[9]?越界，停止） -
子序列 3：
arr[2],?arr[6]?→?[6, 5] -
子序列 4：
arr[3],?arr[7]?→?[2, 7]
-
-
對每個子序列進行插入排序：
-
[8, 1, 4]?→?[1, 4, 8] -
[3, 9]?→?[3, 9]（已有序） -
[6, 5]?→?[5, 6] -
[2, 7]?→?[2, 7]（已有序）
-
-
排序后數組：
將子序列按原位置寫回數組：-
arr[0]=1,?arr[4]=4,?arr[8]=8?→?[1, 3, 5, 2, 4, 9, 6, 7, 8]
-
第 2 輪：gap = 2
-
按間隔 2 分組：
-
子序列 1：
arr[0],?arr[2],?arr[4],?arr[6],?arr[8]?→?[1, 5, 4, 6, 8] -
子序列 2：
arr[1],?arr[3],?arr[5],?arr[7]?→?[3, 2, 9, 7]
-
-
插入排序：
-
[1, 5, 4, 6, 8]?→?[1, 4, 5, 6, 8]（交換 5 和 4） -
[3, 2, 9, 7]?→?[2, 3, 7, 9]（交換 3 和 2，然后 9 和 7）
-
-
排序后數組：
[1, 2, 4, 3, 5, 7, 6, 9, 8]
第 3 輪：gap = 1
-
此時就是普通插入排序，但數組已基本有序：
-
從?
i=1?開始，逐個將元素插入到左側已排序部分。 -
最終結果：
[1, 2, 3, 4, 5, 6, 7, 8, 9]
-
3、希爾排序的實現
代碼示例如下：
import java.util.Arrays;public class ShellSort {/*** 希爾排序（Shell Sort）* @param arr 待排序數組*/public static void shellSort(int[] arr) {if (arr == null || arr.length <= 1) {return; // 如果數組為空或長度≤1，無需排序}int n = arr.length;// 1. 初始化間隔（gap），這里使用 Shell 原始序列：n/2, n/4, ..., 1for (int gap = n / 2; gap > 0; gap /= 2) {// 2. 對每個子序列進行插入排序（從 gap 開始，逐步向右掃描）for (int i = gap; i < n; i++) {int temp = arr[i]; // 當前待插入元素int j;// 3. 插入排序邏輯：比 temp 大的元素向后移動for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap]; // 較大的元素后移}// 4. 將 temp 插入到正確位置arr[j] = temp;}// （可選）打印每輪排序后的數組，方便理解過程System.out.println("Gap = " + gap + ": " + Arrays.toString(arr));}}public static void main(String[] args) {int[] arr = {8, 3, 6, 2, 1, 9, 5, 7, 4};System.out.println("原始數組: " + Arrays.toString(arr));shellSort(arr);System.out.println("排序后數組: " + Arrays.toString(arr));}
}關鍵步驟說明
-
初始化間隔（gap）：
-
初始?
gap = n / 2（Shell 原始序列），之后每次縮小為?gap / 2，直到?gap = 1。 -
例如，數組長度?
n = 9，則?gap?序列為?4 → 2 → 1。
-
-
子序列插入排序：
-
從?
i = gap?開始，逐步向右掃描，對每個子序列進行插入排序。 -
示例（
gap = 4）：-
子序列 1：
arr[0],?arr[4],?arr[8]（即?8, 1, 4?→ 排序后?1, 4, 8） -
子序列 2：
arr[1],?arr[5]（即?3, 9?→ 排序后?3, 9） -
子序列 3：
arr[2],?arr[6]（即?6, 5?→ 排序后?5, 6） -
子序列 4：
arr[3],?arr[7]（即?2, 7?→ 排序后?2, 7）
-
-
-
插入排序邏輯：
-
類似普通插入排序，但步長是?
gap?而不是?1。 -
如果?
arr[j - gap] > temp，則向后移動元素。
-
-
插入最終位置：
-
將?
temp?放到正確的位置?arr[j]。
-
輸出：
原始數組: [8, 3, 6, 2, 1, 9, 5, 7, 4]
Gap = 4: [1, 3, 5, 2, 4, 9, 6, 7, 8]
Gap = 2: [1, 2, 4, 3, 5, 7, 6, 9, 8]
Gap = 1: [1, 2, 3, 4, 5, 6, 7, 8, 9]
排序后數組: [1, 2, 3, 4, 5, 6, 7, 8, 9]4、時間復雜度分析
如下所示：
常見 gap 序列的影響：
-
Shell 原始序列（n/2, n/4, ..., 1）：最壞 O(n2)。
-
Hibbard 序列（1, 3, 7, 15, ..., 2^k -1）：最壞 O(n^(3/2))。
-
Knuth 序列（1, 4, 13, 40, ..., (3^k -1)/2）：平均 O(n^(3/2))。
????????Java 的?
Arrays.sort()?在特定情況下會使用希爾排序的變種（如 TimSort 結合插入排序優化）。
5、希爾排序的優缺點
1、優點
-
比普通插入排序快，尤其是對中等規模數據（n ≤ 10?）。
-
原地排序，空間復雜度 O(1)。
-
適用于部分有序數據，性能接近 O(n)。
2、缺點
-
不穩定排序（可能改變相同元素的相對順序）。
-
時間復雜度依賴 gap 序列，選擇不當可能退化到 O(n2)。
6、適用場景
-
中小規模數據排序（比插入排序更快，比快速排序/歸并排序更節省內存）。
-
嵌入式系統或內存受限環境（因為它是原地排序）。
-
部分有序數據（性能接近線性時間）。
總結
-
希爾排序是插入排序的優化版本，通過分組排序減少元素移動次數。
-
時間復雜度介于 O(n log n) ~ O(n2)，取決于 gap 序列的選擇。
-
適用于中小規模數據，在特定情況下比快速排序/歸并排序更高效。
如果你需要對中等規模數據進行排序，并且希望節省內存，希爾排序是一個不錯的選擇！
參考文章：
1、六大排序算法：插入排序、希爾排序、選擇排序、冒泡排序、堆排序、快速排序-CSDN博客
https://blog.csdn.net/weixin_50886514/article/details/119045154?ops_request_misc=%257B%2522request%255Fid%2522%253A%25220faf03d22b2d125d5f49a4649ad59c85%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=0faf03d22b2d125d5f49a4649ad59c85&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-119045154-null-null.142^v102^control&utm_term=%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F&spm=1018.2226.3001.4187
)
