这是一份关于插入排序及其变种的详细讲解。我为您整理了三种主要的插入排序算法：直接插入排序、折半插入排序和希尔排序。

插入排序算法详解

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

本文将详细介绍三种主要的插入排序方式：

  1. 直接插入排序 (Direct Insertion Sort)
  2. 折半插入排序 (Binary Insertion Sort)
  3. 希尔排序 (Shell Sort)

1. 直接插入排序 (Direct Insertion Sort)

这是最基础的插入排序。它的核心思想是将数组分为“已排序区间”和“未排序区间”。初始时，已排序区间只有一个元素。

算法流程

  1. 从第一个元素开始，该元素可以认为已经被排序。
  2. 取出下一个元素（称为“基准”或 key），在已经排序的元素序列中从后向前扫描。
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
  4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置。
  5. 将新元素插入到该位置后。
  6. 重复步骤 2~5。

适用情况

  • 数据量较小：对于少量元素（如 $n \le 50$），其简单性使得开销很小，甚至优于复杂的排序算法（如快速排序）。
  • 基本有序：如果数组已经“几乎”是有序的，直接插入排序的效率极高，接近 $O(n)$。
  • 需要稳定排序：它不会改变相同元素原本的相对顺序。

缺点

  • 大数据量效率低：平均时间复杂度为 $O(n^2)$。如果有 10000 个数据且完全逆序，效率会非常差。
  • 移动次数多：每次插入都需要移动大量元素。

C++ 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <vector>

void directInsertionSort(std::vector<int>& arr) {
    int n = arr.size();
    // 从第二个元素开始遍历
    for (int i = 1; i < n; ++i) {
        int key = arr[i]; // 待插入的元素
        int j = i - 1;

        // 从后向前扫描已排序区间
        // 如果当前元素大于key，则向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 找到位置，插入 key
        arr[j + 1] = key;
    }
}
````

---

## 2. 折半插入排序 (Binary Insertion Sort)

直接插入排序在查找插入位置时使用的是“顺序查找”。折半插入排序的改进点在于：**使用二分查找（Binary Search）来寻找插入位置**。

### 算法流程

1. 与直接插入排序类似，区别在于查找 `key` 应该插入的位置时。
    
2. 在已排序区间 `[0...i-1]` 中，利用二分查找确定 `key` 的位置。
    
3. 确定位置后，统一将该位置之后的所有元素后移。
    
4. 插入 `key`。
    

### 适用情况

- **比较操作昂贵**：如果比较两个元素的操作非常耗时（例如比较复杂的对象），折半插入排序可以显著减少**比较次数**。
    
- **数据量中等**：比直接插入排序稍好，但并未改变整体的时间复杂度量级。
    

### 缺点

- **移动次数未减少**：虽然减少了“比较”次数，但**移动**元素的次数并没有减少（依然是 $O(n^2)$）。
    
- **不适合链表**：依赖于数组的随机访问特性来进行二分查找，无法用于链表结构。
    
- **可能破坏稳定性**：如果实现时不注意（例如二分查找时对相等元素的处理），可能会变成不稳定的排序。但标准实现通常可以保持稳定。
    

### C++ 代码实现

C++

```cpp
#include <iostream>
#include <vector>

void binaryInsertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int low = 0, high = i - 1;

        // 使用二分查找寻找插入位置
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1; // 保证稳定性，相等时继续向右找
            }
        }

        // low 就是需要插入的位置
        // 统一后移元素
        for (int j = i - 1; j >= low; --j) {
            arr[j + 1] = arr[j];
        }
        arr[low] = key;
    }
}

3. 希尔排序 (Shell Sort)

希尔排序（也称缩小增量排序）是插入排序的一种更高效的改进版本。它打破了时间复杂度 $O(n^2)$ 的限制。

算法流程

  1. 分组：将待排序的数组元素按下标的一定增量（gap）分组。

  2. 组内排序：对每组使用直接插入排序算法排序。

  3. 缩小增量：随着增量逐渐减少，每组包含的关键词越来越多。

  4. 最终排序：当增量减至 1 时，整个文件恰被分成一组，算法终止。

常用的增量序列是 gap = gap / 2（希尔建议），但也有更高效的序列如 Knuth 序列。

适用情况

  • 中等规模数据：在几千到几万规模的数据上表现良好，通常快于 $O(n^2)$ 的算法。

  • 不需要稳定性：当不关心相同元素的相对顺序时。

  • 内存受限：它是一种原地排序算法，不需要大量的额外空间。

缺点

  • 不稳定：这是希尔排序与前两种最大的区别。由于多次跳跃式移动，相同元素的相对位置可能会改变。

  • 增量序列选择复杂：不同的增量序列（Gap Sequence）会显著影响性能。

  • 最坏情况仍较差：虽然平均情况不错，但使用某些增量序列的最坏情况仍接近 $O(n^2)$。

C++ 代码实现

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>

void shellSort(std::vector<int>& arr) {
    int n = arr.size();
    
    // 初始增量设为 n/2，每次减半
    for (int gap = n / 2; gap > 0; gap /= 2) {
        
        // 对每个组进行直接插入排序
        // 注意：这里并不是一个组排完再排下一个组，
        // 而是交替处理（代码写法更简洁）
        for (int i = gap; i < n; ++i) {
            int key = arr[i];
            int j = i;

            // 在当前组内进行“直接插入排序”逻辑
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
        }
    }
}

总结对比

算法名称 平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性 核心特点
直接插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定 简单，适合小数据或基本有序数据
折半插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定 减少了比较次数，但没减少移动次数
希尔排序 $O(n^{1.3})$ (依赖增量) $O(n)$ $O(n^2)$ $O(1)$ 不稳定 通过预处理（大幅度移动）打破了线性限制