HB2-直接插入排序¶

代码实现¶

C
/**
 * 直接插入排序（Direct Insertion Sort）
 * 将每个元素插入到已排序序列的适当位置
 * @param A[] 待排序数组，A[0]作为哨兵位使用
 * @param n   数组有效元素个数
 */
void InsertSort(int A[], int n) { 
    // 从第二个元素开始（i=2），逐个插入到前面的有序序列中
    // 注意：这里使用1-based索引，A[1]是第一个元素
    for (int i = 2; i <= n; i++) {
        A[0] = A[i];  // 将待插入元素暂存到A[0]（哨兵位）

        // 从已排序部分的末尾开始向前查找插入位置
        // 条件：当前元素大于待插入元素时继续移动
        int j;
        for (j = i - 1; A[0] < A[j]; j--) {
            A[j + 1] = A[j];  // 将大于待插入元素的数据向后移动一位
        }

        // 找到插入位置，将元素放入正确位置
        // j+1是因为循环结束后j指向的是第一个不大于A[0]的位置
        A[j + 1] = A[0];
    }
}

算法执行过程图解¶

Text Only

初始数组: [哨兵] [49] [38] [65] [97] [76] [13] [27]
          A[0]  A[1]  A[2]  A[3]  A[4]  A[5]  A[6]

第1轮(i=2): 插入38
比较过程: A[1]=49 > 38, 所以A[2]=A[1]=49, j=0
插入位置: A[1]=38
结果:     [38] [49] [65] [97] [76] [13] [27]

第2轮(i=3): 插入65
比较过程: A[2]=49 < 65, 不进入循环
插入位置: A[3]=65
结果:     [38] [49] [65] [97] [76] [13] [27]

第3轮(i=4): 插入97
比较过程: A[3]=65 < 97, 不进入循环
插入位置: A[4]=97
结果:     [38] [49] [65] [97] [76] [13] [27]

第4轮(i=5): 插入76
比较过程: A[4]=97 > 76 → A[5]=A[4]=97, j=3
          A[3]=65 < 76, 停止
插入位置: A[4]=76
结果:     [38] [49] [65] [76] [97] [13] [27]

第5轮(i=6): 插入13
比较过程: A[5]=97 > 13 → A[6]=A[5]=97, j=4
          A[4]=76 > 13 → A[5]=A[4]=76, j=3
          A[3]=65 > 13 → A[4]=A[3]=65, j=2
          A[2]=49 > 13 → A[3]=A[2]=49, j=1
          A[1]=38 > 13 → A[2]=A[1]=38, j=0
插入位置: A[1]=13
结果:     [13] [38] [49] [65] [76] [97] [27]

复杂度分析¶

时间复杂度：O(n²)¶

详细分析：

最好情况：O(n)
数组已经有序
每次插入时，A[0] >= A[j]，内层循环不执行
只需进行 n-1 次比较
最坏情况：O(n²)
数组逆序排列
第i个元素需要与前面i-1个元素比较并移动
总比较次数：1 + 2 + 3 + ... + (n-1) = n(n-1)/2
平均情况：O(n²)
每个元素平均需要移动其位置一半的距离
平均时间复杂度仍为 O(n²)

空间复杂度：O(1)¶

只使用了常数个额外变量（j）
A[0]作为哨兵位，不增加额外空间
原地排序，空间复杂度为 O(1)

关键知识点延伸¶

1. 哨兵的作用¶

C
A[0] = A[i];  // 哨兵位

优势： - 避免在内层循环中检查数组边界 - 简化代码逻辑 - 提高运行效率

原理： - 哨兵位A[0]存放待插入元素 - 当j递减到0时，A[0]与自身比较必然相等，循环终止 - 无需额外的j >= 1边界判断

2. 算法核心思想¶

"打扑克牌"模型： - 左手持已排序的牌（有序区） - 右手拿新牌（待插入元素） - 从右到左比较，找到合适位置插入

3. 稳定性分析¶

稳定排序：相等元素的相对位置不会改变
当A[0] == A[j]时，循环条件A[0] < A[j]不成立，停止移动
后面的相等元素不会移动到前面

4. 与折半插入排序的比较¶

特性	直接插入排序	折半插入排序
查找方式	顺序查找	二分查找
比较次数	O(n²)	O(n log n)
移动次数	O(n²)	O(n²)
适用场景	小规模数据	数据量较大时优势明显

5. 无哨兵版本实现¶

C
/**
 * 无哨兵的直接插入排序
 */
void InsertSortWithoutSentinel(int A[], int n) {
    for (int i = 1; i < n; i++) {  // 从第二个元素开始
        int temp = A[i];           // 保存待插入元素
        int j = i - 1;

        // 向后移动元素，直到找到插入位置
        while (j >= 0 && temp < A[j]) {
            A[j + 1] = A[j];
            j--;
        }

        A[j + 1] = temp;  // 插入元素
    }
}

6. 优化策略¶

提前终止：

C
// 如果待插入元素不小于前一个元素，说明已在正确位置
if (A[i] >= A[i-1]) continue;

希尔排序：插入排序的改进版
通过增量序列先进行粗略排序
最后用增量1进行直接插入排序
时间复杂度可优化到O(n^1.3)

7. 适用场景¶

小规模数据：n < 50时效率较高
基本有序数据：接近有序时接近O(n)时间
在线算法：可以边接收数据边排序
稳定排序需求：需要保持相等元素的相对顺序

算法特点总结¶

简单高效：对于小规模或部分有序数据非常有效
稳定排序：保持相等元素的相对位置
原地排序：只需要常数级额外空间
自适应性：数据越有序，运行越快
在线算法：可以在接收数据的同时进行排序

记忆要点¶

索引从2开始：因为A[0]是哨兵，A[1]是第一个元素
哨兵技巧：用A[0]暂存数据，简化边界处理
移动方向：从后往前移动大于待插入元素的数据
插入位置：A[j+1]，因为循环结束后j指向的是第一个不大于的位置