排序算法‌ 之‌ 插入排序（Insertion Sort）

排序算法‌ 之‌ 插入排序（Insertion Sort）

1. 基础概念

1.1 插入排序的定义

插入排序是一种基于比较的排序算法，其核心思想是将数组划分为已排序部分和未排序部分，通过逐步从未排序部分提取元素并插入到已排序部分的合适位置，实现整体排序。它是一种稳定排序算法。

1.2 插入排序的特点

• 时间复杂度：最优 O(n)、最差 O(n²)、平均 O(n²)。
• 空间复杂度：O(1)，无需额外存储空间。
• 适用于数据量小或数据基本有序的情况。
• 算法稳定性：稳定。

1.3 使用场景

插入排序适用于小型数据集或当输入数据接近排序状态时效率较高。例如：

• 对少量记录排序（如 10 个以下的数组）。
• 需要稳定排序的场景（保持相同键值的元素相对顺序）。

2. 实现与操作

2.1 核心操作实现

以下是插入排序的实现代码，使用 C 语言编写，包含详细注释。

#include <stdio.h> // 插入排序函数 void insertionSort(int arr[], int n) { 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; } } // 打印数组 void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } // 主函数 int main() { int arr[] = {12, 11, 13, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); printf("原始数组: "); printArray(arr, n); insertionSort(arr, n); printf("排序后数组: "); printArray(arr, n); return 0; } </stdio.h>

2.2 代码详解

• 初始化 key 为当前待插入的元素。
• 通过 while 循环向后移动比 key 大的元素。
• 在循环结束后，将 key 插入到正确位置。

3. 时间与空间复杂度分析

3.1 时间复杂度

• 最优：O(n)，当数组本身已排序。
• 最差：O(n²)，当数组逆序。
• 平均：O(n²)，随机排列。

3.2 空间复杂度

空间复杂度为 O(1)，无需额外存储，仅使用了常数级别的辅助变量。

4. 优缺点与局限性

4.1 优点

• 简单易实现，代码量少。
• 对小数据集效率较高。
• 稳定排序。

4.2 缺点与局限性

• 对于大数据集效率低。
• 大量元素移动时，性能开销较大。

5. 常见应用场景

5.1 实际应用

插入排序可用于基于少量数据集的实时排序。

6. 代码编译与运行

6.1 编译命令

使用以下命令编译代码：

gcc -o insertion_sort insertion_sort.c

6.2 测试用例

输入数组 {12, 11, 13, 5, 6}，输出如下：

    原始数组: 12 11 13 5 6
    排序后数组: 5 6 11 12 13