定义

希尔排序（Shell Sort） 是一种分组插入排序算法。它通过先将待排序序列按一定增量分组，对每组分别进行插入排序，然后逐步缩小增量，最终增量为1时进行一次普通插入排序。这样可以让元素快速移动到接近最终位置，提高排序效率。

设计思路

1. 定义一个顺序表：

---

2. 增量为4

定义下标与增量：
- i：移动下标
- j：对比下标
- increment: 分组增量，初始为（1/3长度 +1）

如下图左1所示。

increment初始为 4，即4个元素为一组，对每组做插入排序时，组内第一个元素（下标为 1~increment）不需要移动，直接从下一个元素（i = increment+1）开始，依次和组内前面的元素比较并插入到合适位置。

首先元素 3(i=5) < 9(j=1)，所以把 3 放到 i=0 位置（上图右1），此位置作为一个临时位置，用于交换元素。此时 j 开始往右不能在构成一个新的完整分组 （j-=increment ≠ 4），所以直接交换 3 和 9 的(上图右2)。

---

完成一组插入排序后 i++，如下图所示。元素 1 < 7 ，所以不经行插入排序。

---

i++，此时 i=7，j=3（i-increment）（下图左1）。 因为元素 4 < 5， 所以把4放到i=0的位置（下图右1）。（j-=increment ≠ 4） 此时 j 开始往右不能在构成一个新的完整分组 ，所以直接交换 5 和 4 （下图右2）。

---

i++，此时 i=8，j=4（下图左1）。分析通上。

---

i++, 此时 i=9，j=5（下图左1）。因为元素 2 < 9， 所以把元素 2 放到 i=0 的位置（下图右1），把元素 9 挪到 i=9 的位置（下图右2），（j-=increment = 1） 此时 j 开始往右可以在构成一个新的完整分组（下图右3），即位置 1~4 为一个新的分组，继续比较 j=1 和 i = 0 的元素，元素 2 < 3，所以元素 3 挪到 i=5 的位置（下图右4），元素 2 挪到 i=1 的位置（下图右5）。

---

3. 增量为2
后续同上

C代码实现

#include <stdio.h>

#define MAXSIZE 9
typedef struct {
  int array[MAXSIZE + 1];
  int length;
} SqList;

void ShellSort(SqList *L) {
  int i, j;
  int increment = L->length;

  do {
    increment = increment / 3 + 1;              /* 计算增量 */ 

    for (i = increment + 1; i <= L->length; i++) {
      if (L->array[i] < L->array[i - increment]) {
        L->array[0] = L->array[i];                   /* 将当前元素存入临时变量 */ 
        for (j = i - increment; j > 0 && L->array[0] < L->array[j];
             j -= increment)
          L->array[j + increment] = L->array[j];        /* 将大于当前元素的元素向后移动 */
        L->array[j + increment] = L->array[0];          /* 将当前元素放入合适位置 */
      }
    }
    printf("当前增量: %d  当前数组: ", increment);
    for (int k = 1; k <= L->length; k++)
      printf("%d ", L->array[k]);
    printf("\n");
  } while (increment > 1);
}

int main(void) {
  SqList L = {{0, 9, 1, 5, 8, 3, 7, 4, 6, 2}, 9}; /* 初始化顺序表 */ 
  ShellSort(&L);                                  /* 调用希尔排序函数 */ 

  for (int i = 1; i <= L.length; i++)
    printf("%d ", L.array[i]);
  printf("\n");

  return 0;
}

当前增量: 4, 当前数组: 2 1 4 6 3 7 5 8 9 
当前增量: 2, 当前数组: 2 1 3 6 4 7 5 8 9 
当前增量: 1, 当前数组: 1 2 3 4 5 6 7 8 9 
1 2 3 4 5 6 7 8 9 

[Done] exited with code=0 in 0.366 seconds

---

复杂度

• 最坏情况：常用的增量（如 increment = increment/3+1）下，最坏情况时间复杂度约为 O(n^1.5) 到 O(n^2)。
• 最好情况：如果数据本身接近有序，复杂度可接近 O(n)。