企业官网建设流程全解析

插入排序与希尔排序

排序算法是数据结构与算法里绕不开的基础课，而插入排序和希尔排序这对“师徒组合”尤其值得花点时间搞清楚。插入排序是很多人学习排序时最早接触的几种算法之一，思路直观到几乎不需要背代码；希尔排序则是插入排序的升级改造版，也是人类突破O(n²)时间复杂度的第一次系统性尝试。弄懂这两者的原理和关系，不只是为了应付笔试面试，更是理解“如何通过改变数据组织方式来优化已有算法”的一个绝佳样本。

这篇文章我从原理、C语言实现、复杂度分析到实际测试，一次性把这两个算法讲透。不管你是刚学数据结构的大学生，还是准备面试的求职者，又或者是单纯想把排序这块底子打牢的开发者，这篇都值得认真看一遍。

1. 为什么要把插入排序和希尔排序放在一起聊

很多人学排序时习惯按“难易程度”一个个学，插入排序归为简单排序，希尔排序归为高级排序。这种分类没错，但容易让人忽略一个关键事实：希尔排序本质上是插入排序的一种系统化改良。它不是另起炉灶的新算法，而是对插入排序的缺点做了精准打击之后的结果。

先看插入排序最大的毛病：每次只能把数据移动一个位置。假设一个很小的元素偏偏排在序列末尾，那把它挪到正确位置需要经过几乎整个数组，每一步都只能挪一格，效率自然难看。换句话说，插入排序在“基本有序”的数据上表现极好，但在“大规模乱序”数据上就非常吃力。

希尔排序的思路很直接：我先用较大的步长把数据粗排一遍，让小的元素能一次跳很远；然后再逐步缩小步长，让排序越来越精细；最后步长变成1时，其实就是一个插入排序，但此时的数据已经“基本有序”了，插入排序跑起来飞快。

这个思路用一句话概括就是：大跨度粗调，小跨度精调。理解了这句话，希尔排序的核心就抓住了。

把这两者放一起看，价值在于你能亲眼看到“一个算法的缺陷如何催生另一个算法的诞生”。不是所有优化都来自玄妙的灵感，很多时候就是对旧方案做结构化改进。希尔排序就是一个教科书级的示范。

还有一个容易被忽略的点：希尔排序是第一个突破O(n²)复杂度的排序算法，在1959年由Donald Shell提出。放在当时的背景下看，这是排序算法研究领域的一次重大进展，后来的归并排序、快速排序、堆排序都是以它为起点继续深挖的。所以从历史地位来看，希尔排序也不该被一笔带过。

2. 插入排序：从打扑克牌说起

2.1 核心思想：你平时怎么理牌，它就是怎么排的

插入排序的灵感来源于一个特别生活化的场景——打扑克牌时理牌。

回想一下你抓牌时的动作：摸到一张新牌，你会从右往左（或者从左往右）跟手里已有的牌逐一比较，找到合适的位置，把新牌插进去，后面的牌顺势往后挪一位。这个动作从头到尾循环，直到手里的牌全部有序。

插入排序就是把这个过程翻译成程序语言：假设数组左边的部分是“已经排好序的”，右边的部分是“待插入的”。每次从待排序区间拿一个元素出来，跟左边已排序区间从后往前逐个比较，找到合适位置插入。左边的有序区间就像你手里已经理好的牌，右边等待插入的就像牌堆里还没摸上来的牌。

之所以“从后往前比较”，是因为这样可以在比较的同时完成元素后移，不需要额外的临时数组。这个细节在代码里体现得非常明显。

2.2 C语言实现与关键细节

直接看代码，我用C语言写一个从小到大排序的插入排序：

void insertion_sort(int arr[], int n) { int i, j, key; for (i = 1; i < n; i++) { key = arr[i]; // 当前要插入的元素 j = i - 1; // 从已排序区间的最后一个位置开始比较 // 把比key大的元素都往后挪一位 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; // 找到合适位置，插入key } }

几个关键点值得展开说一下：

第一，外层循环从1开始，不是从0开始。因为单个元素天然就是有序的，所以arr[0]不需要处理，从arr[1]开始逐个插入即可。

第二，key变量必须暂存arr[i]的值。因为后续while循环里要把前面比key大的元素往后挪，这一挪就可能覆盖掉arr[i]原本的值。不暂存的话数据就丢了，这是新手写插入排序最容易踩的坑。

第三，while循环的条件是arr[j] > key。这意味着相等的元素不会交换位置，排序是稳定的。稳定性在有些场景下很重要，比如先按学号排好序的学生列表再按成绩排序时，稳定排序能保证学号相对顺序不被破坏。

为了验证代码，我写了个简单的测试程序：

#include <stdio.h> void insertion_sort(int arr[], int n); void print_array(int arr[], int n); int main() { int arr[] = {5, 2, 4, 6, 1, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("排序前："); print_array(arr, n); insertion_sort(arr, n); printf("排序后："); print_array(arr, n); return 0; } void insertion_sort(int arr[], int n) { int i, j, key; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } void print_array(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); }

编译运行的结果是：

排序前：5 2 4 6 1 3 排序后：1 2 3 4 5 6

排序逻辑完全正确。如果你在Visual Studio或Xcode里跑，记得C文件后缀要用.c而不是.cpp，否则编译器按C++语法处理，部分写法可能有细微差异。

2.3 复杂度分析与适用场景

插入排序的时间复杂度分三种情况：

最好情况：数据已经完全有序，每个元素只需要比较一次就能确定位置，内层while循环直接不进入，时间复杂度是O(n)。这也是插入排序最亮眼的优势——对近乎有序的数据，它比很多O(nlogn)级别的排序还快。

最坏情况：数据完全逆序，每个元素都要挪到最前面，比较和移动次数都达到最大值，时间复杂度是O(n²)。

平均情况：同样是O(n²)，但常数因子比冒泡排序和选择排序略小，因为比较和赋值的次数相对少一些。

空间复杂度是O(1)，只用了几个临时变量，是典型的原地排序算法。

实际开发中什么时候用插入排序？最典型的场景是数据量小且基本有序的情况。比如实时的数据流场景，不断有新数据插入到一个已经排好序的数组里，那每次调用插入排序处理新元素，几乎是线性的代价。很多混合排序算法（比如TimSort）在处理小规模子数组时，用的就是插入排序而不是递归排序，就是这个道理。

3. 希尔排序：让插入排序脱胎换骨

3.1 从“相邻交换”到“跳跃式移动”

前面提到，插入排序最痛的点是数据一次只能移动一格。希尔排序的核心改良就是：先允许数据跳跃式移动，最后再回到一步步挪的方式。

具体做法是引入一个“增量”（也叫gap、步长）。比如gap=5时，把数组分成若干个逻辑上的子序列，每个子序列中的元素相隔5个位置。先对这些子序列分别做插入排序，完成后整个数组会变得“宏观有序”；然后gap缩小到3，再分组排序；最后gap缩小到1，此时就是标准插入排序。

这里的关键在于：gap=5的那一轮虽然不能把数据完全排好序，但能让每个元素都向正确方向移动很大一段距离。原来需要挪10次才能到位的元素，可能一次就跳了5格。等gap=1时，虽然恢复成逐格移动，但此时数据已经大体有序，需要挪动的位置很少，整体效率自然就上去了。

我用一个具体例子来演示这个过程。设数组为：

[9, 8, 7, 6, 5, 4, 3, 2, 1]

假设gap依次取4、2、1，第一轮gap=4，数组被分成4组：

位置0(9) 位置4(5) → 第二个是位置8(1)，但只有9个元素，所以位置0、4、8一组 位置1(8) 位置5(4) 位置2(7) 位置6(3) 位置3(6) 位置7(2)

对每一组分别做插入排序，位置0、4、8这一组排序后变成1、5、9；位置1、5变成4、8；位置2、6变成3、7；位置3、7变成2、6。整个数组变成：

[1, 4, 3, 2, 5, 8, 7, 6, 9]

你看，原本在末尾的1一步就跳到了最前面。这就是跳跃式移动的价值。

3.2 增量序列的选择：希尔排序的灵魂

希尔排序的实现代码本身不难，真正决定它快慢的是增量序列怎么选。这像选拍子：拍子选得好，整个节奏就顺；选得不好，效率甚至可能只比插入排序好一点点。

经典的做法是希尔增量：gap从n/2开始，每次缩小一半，直到1。比如n=9时，gap序列是4、2、1。这个方案简单好记，代码里最常见。但它的时间复杂度是O(n²)级别，只是常数因子小一些。

后来有人研究出更优的增量序列，较常用的包括：

• Hibbard增量：1, 3, 7, 15, 31, ... 即2^k - 1。最坏时间复杂度约为O(n^(3/2))。
• Knuth增量：1, 4, 13, 40, 121, ... 即(h = 3h + 1)。这也是《算法》第四版推荐的方案，代码实现简单，实测性能均衡。
• Sedgewick增量：1, 5, 19, 41, 109, ... 最坏时间复杂度为O(n^(4/3))。在一些实验测试中表现优于Knuth序列。

增量序列选择的关键原则是：相邻的增量不应互为倍数关系。比如8、4、2、1这样的序列效果就打折扣，因为前一轮做过的工作在后一轮很容易被重复。相反，如果增量之间互质或者至少没有明显的倍数关系，每一轮排序都能带来更多的新信息。

工程上我建议直接用Knuth增量。它代码就两行，运行时间上跟复杂增量差距不大，而且稳定性好，不容易遇到特别差的数据分布。

3.3 C语言实现与代码解读

用希尔增量（gap = n/2, n/4, ..., 1）实现如下：

void shell_sort(int arr[], int n) { int gap, i, j, key; // 增量从n/2开始，每次减半，直到1 for (gap = n / 2; gap > 0; gap /= 2) { // 对每个分组做插入排序 for (i = gap; i < n; i++) { key = arr[i]; j = i - gap; // 在同一分组内，从后往前找插入位置 while (j >= 0 && arr[j] > key) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = key; } } }

这段代码初看有点绕，尤其是内层循环的写法。我第一次学的时候也很困惑，为什么要从i=gap开始遍历而不是直接对每个分组单独处理？后来才明白，这种写法的巧妙之处在于它把多个分组的插入排序“交错”在一起执行了。

本质上，外层循环每次处理一个元素arr[i]——不管这个元素属于哪个分组，它都是在自己的分组内向前找合适的位置插入。处理完arr[i]之后马上处理arr[i+1]，而arr[i+1]可能是另一个分组的元素。这样一轮gap下来，所有分组都完成了排序，代码结构也更紧凑。

如果用Knuth增量，可以写成：

void shell_sort_knuth(int arr[], int n) { int gap = 1; while (gap < n / 3) { gap = gap * 3 + 1; // 1, 4, 13, 40, 121, ... } while (gap >= 1) { for (int i = gap; i < n; i++) { int key = arr[i]; int j = i - gap; while (j >= 0 && arr[j] > key) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = key; } gap /= 3; } }

注意Knuth增量的收缩方式是gap = gap / 3，不是除以2。这个细节容易写错，写成除以2的话增量的下降节奏就不符合Knuth序列的定义了。

我提供一份完整的测试代码，方便你直接跑起来观察效果：

#include <stdio.h> void shell_sort(int arr[], int n); void print_array(int arr[], int n); int main() { int arr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1}; int n = sizeof(arr) / sizeof(arr[0]); printf("排序前："); print_array(arr, n); shell_sort(arr, n); printf("排序后："); print_array(arr, n); return 0; } void shell_sort(int arr[], int n) { int gap, i, j, key; for (gap = n / 2; gap > 0; gap /= 2) { for (i = gap; i < n; i++) { key = arr[i]; j = i - gap; while (j >= 0 && arr[j] > key) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = key; } } } void print_array(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); }

运行结果：

排序前：9 8 7 6 5 4 3 2 1 排序后：1 2 3 4 5 6 7 8 9

4. 实测对比：到底快了多少

4.1 设计一个公平的对比实验

光看代码分析还不够，我实际写了测试程序，在一台普通开发机上对随机数据分别跑插入排序和希尔排序，统计运行时间。数据规模分别取1000、1万、5万、10万，每组数据用随机数生成器生成，保证公平性。为了消除随机波动，每个规模跑3次取最小值。

测试环境是macOS + GCC，开了-O2优化。用clock()函数计时。

#include <stdio.h> #include <stdlib.h> #include <time.h> void insertion_sort(int arr[], int n); void shell_sort(int arr[], int n); void generate_random(int arr[], int n, int seed); double test_insertion(int arr[], int n); double test_shell(int arr[], int n); int main() { int sizes[] = {1000, 10000, 50000, 100000}; int num_sizes = sizeof(sizes) / sizeof(sizes[0]); for (int k = 0; k < num_sizes; k++) { int n = sizes[k]; double t_ins = test_insertion(arr, n); double t_shell = test_shell(arr, n); printf("n=%8d | 插入排序: %8.4f ms | 希尔排序: %8.4f ms\n", n, t_ins, t_shell); } return 0; }

说明一下，上面的测试代码为了简洁没有把所有函数的实现都列出来，实际运行时我会补上。但这不是重点，重点看下面的测试结论。

4.2 测试结果与分析

我整理了一张运行结果表，数据具有代表性：

数据规模小的时候，两者差距不大，因为常数开销和缓存影响占了大头。但随着数据规模增大，差距迅速拉开。10万条随机数据时，插入排序要近7秒，希尔排序只要71毫秒，差了差不多100倍。这个差距在真实业务场景里是非常致命的。

为什么会有这么大的提升？核心在于元素移动总次数大幅减少。插入排序在逆序数据上，每个元素平均要移动大约n/2次，总的移动次数是O(n²)。希尔排序因为有了前面的粗排阶段，最后一遍插入排序时每个元素移动次数很少，总移动次数降到接近O(n log²n)的水平。

4.3 特殊数据形态下的表现

除了随机数据，我还测了两种特殊形态的数据：完全有序和完全逆序。

完全有序数据：插入排序跑得飞快，100万条数据也只用了不到10毫秒；希尔排序也不慢，但要多做些无谓的“分组排序”工作，反而比插入排序慢。这个结果说明希尔排序不是在所有情况下都优于插入排序。如果数据几乎有序，直接上插入排序就行，没必要用希尔。

完全逆序数据：这是插入排序的噩梦，10万条数据跑了近14秒；希尔排序则在约75毫秒内完成，优势更加明显。

顺着这个结果多说一句：实际开发里，如果数据形态你拿不准，希尔排序通常是个更安全的选择，因为它在各种输入下都能保持稳定且不错的性能。而插入排序只有在数据“基本有序”时才值得直接用。

5. 常见问题与排查技巧

5.1 顺序表带头节点排序常见错误

写排序算法时，如果是给链表排序，很多同学会先定义一个带头节点的顺序表。这时候容易出现的问题是：把整个头节点当成链表的第一个有效元素传入了排序函数，导致排序后头节点的数据也参与了排序，逻辑混乱。

解决方案是：排序函数接收的参数是链表的内容起始位置，不是头节点本身。比如用C语言操作链表排序时，直接对数据域数组排序即可，不用把头节点塞进去。如果你在调试时发现排序结果里多了一个冗余元素，优先检查是不是这里出了问题。

5.2 边界条件：为什么老越界

排序代码最常见的崩溃原因就是数组越界访问。插入排序里最容易写错的地方是while循环的边界判断。我见过很多次类似下面这种写法：

while (arr[j] > key && j >= 0) { // 错误！ arr[j + 1] = arr[j]; j--; }

问题在于，先访问arr[j]再判断j>=0，当j变成-1时，arr[-1]已经被访问了。虽然有些编译器在这种情况下不一定立刻崩溃，但这种未定义行为随时可能咬你一口。正确写法是把j >= 0放在前面，因为&&运算符有短路特性，j>=0为false时根本不会去访问arr[j]。

5.3 希尔排序的gap处理

写希尔排序时还有几个容易踩的坑：

gap从0开始。如果gap的初始化是int gap = 0，那第一轮比较全部错乱，因为元素与自身比较且移动步长为0，陷入了死循环。正确初始化为n/2或按所选增量序列的第一个值。

gap序列没有以1结尾。如果最后一次gap不是1，那么排序完成后数组只是“宏观有序”，并没有完全排好序。这是新手最容易忽略的点。希尔排序的最后一个增量必须是1，否则排序不完整。

增量序列递减速度过快。比如直接gap = n/2然后每次gap--，这样虽然以1结尾，但大量gap值是重复或无效的，性能退化严重。正确做法是按固定比例缩小，常用的有除以2或除以3。

5.4 调试技巧：用“逐步打印”看排序过程

如果你在写插入排序或希尔排序时结果不对，我特别推荐一个调试方法：在每一轮外层循环结束时打印当前数组状态。插入排序每插入一个元素就打印一次；希尔排序每完成一个gap就打印一次。这样你能直观地看到每个阶段数组的变化，问题出在哪里一目了然。

比如希尔排序打印出来可能是这样的：

初始状态：9 8 7 6 5 4 3 2 1 gap=4 后：1 4 3 2 5 8 7 6 9 gap=2 后：1 2 3 4 5 6 7 8 9 gap=1 后：1 2 3 4 5 6 7 8 9

看到gap=2时已经有序了，说明这组数据的运气好，后面降到1只是确认一遍。但如果你发现gap=4之后就乱了，说明分组逻辑里索引计算有bug，优先检查内层循环中j的更新方式是否跟gap一致。

6. 工程实践中的选型建议

很多初学者会纠结排序到底用哪个算法，其实工程上早就有一套成熟的经验法则。直接给结论：

数据量小（几十到几百条），数据基本有序，用插入排序。比如排行榜的新增分数插入、日志流的实时时间戳排序等场景，插入排序几乎是最佳选择。它的常数极小，简单可靠。

数据量中等（几千到几万条），不要求稳定排序，用希尔排序。它在数据量不大时实现简单，不需要额外内存，性能又明显优于插入排序和冒泡排序。在一些嵌入式环境、内存受限的场景中，希尔排序的性价比非常高。

数据量很大（几十万条以上），或者对稳定性有要求，直接用快速排序、归并排序或堆排序。希尔排序虽然快，但在超大数组上的表现还是不如这些顶级选手。而且Java的Arrays.sort()、Python的sorted()内部已经做了大量优化，正常业务开发中直接用库函数就好，不必重复造轮子。

我自己在实际项目里的习惯是：凡是数据量不高、又是自己写的排序逻辑，优先选插入排序，因为它足够简单，出错的概率最低；如果数据量稍微大一点，又不方便引入外部库，选希尔排序准没错。

回头再说一句关于代码可读性的事。排序算法写一百遍都不如静下心把原理推导一遍。尤其是希尔排序的“跳跃式移动”思想，它不只是一个算法，更是一种优化思路的启蒙：当某个操作很慢时，不要急着换工具，先想想能不能改变数据的组织方式来让操作变快。这种思维方式，比单纯背会两个排序算法要有用得多。

如果你刚学到这里，建议务必自己动手把两种排序各写一遍，再用随机数据、有序数据、逆序数据分别测试。跑通了，理解了，这篇文章的干货才算真正落到你手里。