软考-软件设计师：排序算法-插入类排序：希尔（Shell）排序（优化版插入排序） 作者：马育民 • 2026-02-06 10:26 • 阅读：10004 # 介绍 希尔（Shell）排序，是 **插入排序** 的 **高效** 改进版。过 **分组 预排序** 让数组整体接近有序，最后用普通 **插入排序** 完成最终排序，大幅降低插入排序的移动次数，时间效率远高于基础插入排序。 # 普通插入排序的缺点是 数组 **无序程度越高**、**元素个数越多**，元素需要 **移动的次数就越多**（比如一个很小的数在数组末尾，需要一步步移到开头）。 # 希尔排序算法 希尔排序针对这个问题做了优化，核心是 **步长（gap）**分组： 1. 选择一个步长序列（比如n/2、n/4、n/8...1，n 是数组长度），按步长将数组分成多个子组； 2. 对每个子组分别做插入排序（分组预排序），让数组整体逐渐接近有序； 3. 逐步缩小步长，重复 “分组 + 插入排序”，直到步长为1； 4. 步长为1时，整个数组就是一个子组，此时做一次普通插入排序（数组已接近有序，这次排序几乎无额外移动）。 **提示：** 一般取 `n/2`，如果结果为偶数，则加 `1` # 例子 已序列 `[49,38,65,97,76,13,27,48,55,4]` 为例（长度为 `10`），进行排序演示 ### 第1阶段 ##### 分组 步长 `gap = 10(第一次根据元素数量)//2 = 5`，**索引差为 `5` 的元素分为一组**，共分成 `5` 组（每组 `2` 个元素），分组结果如下： 分组情况 : - 组 1：索引 `0` 与索引 `5` 组成一组，即：`[49,13]` - 组 2：索引 `1` 与索引 `6` 组成一组，即：`[38,27]` - 组 3：索引 `2` 与索引 `7` 组成一组，即：`[65,48]` - 组 4：索引 `3` 与索引 `8` 组成一组，即：`[97,55]` - 组 5：索引 `4` 与索引 `9` 组成一组，即：`[76,4]` ##### 排序 执行循环，对每个 **子组** 执行 **插入排序** - 对 组1 `[49,13]` 执行插入排序，由于 `49>13`，将这两个元素 **互换位置**，执行后数组： `[13,38,65,97,76,49,27,48,55,4]` - 对 组2 `[38,27]` 执行插入排序，由于 `38>27`，将这两个元素 **互换位置**，执行后数组： `[13,27,65,97,76,49,38,48,55,4]` - 对 组3 `[65,48]` 执行插入排序，由于 `65>48`，将这两个元素 **互换位置**，执行后数组： `[13,27,48,97,76,49,38,65,55,4]` - 对 组4 `[97,55]` 执行插入排序，由于 `97>55`，将这两个元素 **互换位置**，执行后数组： `[13,27,48,55,76,49,38,65,97,4]` - 对 组5 `[76,4]` 执行插入排序，由于 `76>4`，将这两个元素 **互换位置**，执行后数组： `[13,27,48,55,4,49,38,65,97,76]` 本次结果： ``` [13,27,48,55,4,49,38,65,97,76] ``` ### 第2阶段 ##### 分组 步长 `gap = 5(上一次的步长)//2 = 2`，**索引差为 `5` 的元素分为一组**，共分成 `2` 组（每组 `5` 个元素），分组结果如下： 分组情况 : - 组 1（偶数索引：0、2、4、6、8）→ [13,48,4,38,97] - 组 2（奇数索引：1、3、5、7、9）→ [27,55,49,65,76] ##### 对 组1 排序 对 组1 `[13,48,4,38,97]` 执行 **插入排序**，初始时： - 已排序序列：`13` - 未排序序列：`48,4,38,97` --- 1.执行内层循环，比较 **未排序的首元素 `48`**，与 **已排序序** 的 **元素逐一比较** - 与 **已排序序列最后一个元素：`13`** 比较，因为`48>13`，所以应该将 `48` 插入到 `13` 的后面，由于原本顺序就是这样，所以不动。 本轮结果：：`[13,48,4,38,97]` - 已排序序列：`13,48` - 未排序序列：`4,38,97` --- 2.执行内层循环，比较 **未排序的首元素 `4`**，与 **已排序序** 的 **元素逐一比较** - 与 **已排序序列最后1个元素：`48`** 比较，因为`48>4`，所以应该将 `48` 后移到 `4` 的位置，数组变为：`[13,27,48,55,48,49,38,65,97,76]` - 与 **已排序序列第1个元素：`13`** 比较，因为`13>4`，所以应该将 `13` 后移到 **`48` 的 原位置**，数组变为：`[13,27,13,55,48,49,38,65,97,76]` - 已遍历完 **已排序序列**，将 `4` 插入到 `13` 的位置，数组变为：`[4,27,13,55,48,49,38,65,97,76]` 本轮结果：：`[4,13,48,4,38,97]` - 已排序序列：`4,13,48` - 未排序序列：`38,97` 后面执行过程略 ##### 对 组2 排序 执行过程同 组1 此时结果：`[4, 27, 13, 49, 38, 55, 48, 65, 97, 76]` ### 第三阶段 ##### 分组 步长 `gap = 2(上一次的步长)//2 = 1`，**索引差为 `1` 的元素分为一组**，此时执行的就是 **普通插入排序**，但因为数组已 **基本有序**，几乎没有大量元素移动，这也是希尔排序高效的关键。 执行过程，同插入排序，略 最终结果：`[4, 13, 27, 38, 48, 49, 55, 65, 76, 97]` # 时间复杂度 $$O(n^2)$$ ### 最好 $$O(n^{1.25})$$ ### 最坏 $$O(n^2)$$（但实际工程中几乎不会出现） ### 平均 $$O(n^{1.3})$$ # 空间复杂度 O(1) # 是否稳定 不稳定，因为跨 n 个元素取值 原文出处：http://malaoshi.top/show_1GW2jH6zMLZH.html