直接插入排序讲解

直接插入排序

• 定义
• 算法步骤
• 复杂度分析
• 代码示例（C）
• • 代码分析
  • • 1. 打印数组模块
    • 2. 直接插入排序模块
    • 3. 主函数模块
  • 图示过程
  • • 初始状态
    • 第一轮排序（插入 `11`）
    • 第二轮排序（插入 `13`）
    • 第三轮排序（插入 `5`）
    • 第四轮排序（插入 `6`）
  • 运行流程图解
  • 最终结果
• 优缺点

定义

直接插入排序是一种简单直观的排序算法，适用于少量数据的排序任务。它的工作原理是将数组分为已排序和未排序两部分，然后将未排序部分的每个元素按顺序插入到已排序部分的适当位置。

算法步骤

1. 初始化： 将第一个元素视为已排序部分，其余元素为未排序部分。
2. 遍历未排序部分：
   • 从第二个元素开始，依次取出每个元素。
   • 将该元素插入到前面已排序部分的正确位置。
3. 插入：
   • 从后向前扫描已排序部分，找到插入位置。
   • 如果扫描到的元素比当前元素大，则将该元素后移一位。
4. 重复步骤 2 和 3，直到所有元素都插入完成。

复杂度分析

• 时间复杂度：

  • 最好情况：数组已近乎有序，比较 O ( n ) O(n) O(n) ，移动 O ( 1 ) O(1) O(1) 。总复杂度为 O ( n ) O(n) O(n) 。
  • 最坏情况：数组完全逆序，比较和移动均为 O ( n 2 ) O(n^2) O(n2) 。总复杂度为 O ( n 2 ) O(n^2) O(n2)。
  • 平均情况：比较和移动均为 O ( n 2 ) O(n^2) O(n2) 。

• 空间复杂度： O ( 1 ) O(1) O(1) ，因为不需要额外的空间。

• 稳定性： 稳定，因为在插入过程中，不会改变相同元素的相对顺序。

代码示例（C）

以下是直接插入排序的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;

        // 向前扫描已排序部分，寻找插入位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];  // 将大于 key 的元素后移
            j--;
        }
        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;
}

代码分析

1. 打印数组模块

函数原型：

void printArray(int arr[], int n);

功能说明：

• 负责遍历并打印数组的内容。
• 用于查看数组排序前和排序后的结果。

代码分析：

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]); // 打印数组的每个元素，之间用空格隔开
    }
    printf("\n"); // 打印换行符，结束当前行
}

输入参数：

• arr[]: 待打印的数组。
• n: 数组的长度。

关键点：

• 使用 for 循环遍历数组，逐个打印元素。
• 每个元素后面用空格隔开，打印完成后换行。

作用：

• 帮助调试和验证排序结果。

2. 直接插入排序模块

函数原型：

void insertionSort(int arr[], int n);

功能说明：

• 对数组进行排序，将数组分为已排序和未排序两部分。
• 每次从未排序部分取出一个元素，插入到已排序部分的适当位置。

代码分析：

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {  // 遍历未排序部分，从第二个元素开始
        int key = arr[i];  // 记录当前待插入的元素
        int j = i - 1;     // j 是已排序部分的最后一个元素索引

        // 向前扫描已排序部分，找到 key 应插入的位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // 将大于 key 的元素后移一位
            j--;                 // 向前继续比较
        }

        arr[j + 1] = key; // 插入 key 到正确位置
    }
}

输入参数：

• arr[]: 待排序的数组。
• n: 数组的长度。

关键点：

1. 外层循环：

   • for (int i = 1; i < n; i++): 遍历数组的未排序部分，从第二个元素开始。
   • 第一个元素默认视为已排序部分，无需处理。

2. 保存待插入元素：

   • int key = arr[i];：保存当前待插入的元素，避免覆盖问题。

3. 内层循环：

   • while (j >= 0 && arr[j] > key)：
     • 从后向前扫描已排序部分，找到插入位置。
     • 如果当前元素大于 key，则将其后移一位，为 key 腾出位置。

4. 插入操作：

   • arr[j + 1] = key;：将 key 插入到正确位置。

3. 主函数模块

函数原型：

int main();

功能说明：

• 定义数组，调用排序和打印函数。
• 展示排序前和排序后的数组。

代码分析：

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; // 程序正常结束
}

关键点：

1. 数组初始化：

   • int arr[] = {12, 11, 13, 5, 6};：定义并初始化待排序数组。

2. 数组长度计算：

   • sizeof(arr) / sizeof(arr[0]): 数组总字节数除以单个元素的字节数，计算数组长度。

3. 函数调用顺序：

   • 调用 printArray 打印排序前数组。
   • 调用 insertionSort 执行排序。
   • 再次调用 printArray 打印排序后的数组。

图示过程

初始状态

数组为 {12, 11, 13, 5, 6}，我们把第一个元素 12 看作是初始已排序部分，后面的元素逐个插入到这个已排序部分中。

第一轮排序（插入 11）

• 此时 i = 1，key = 11，j = 0。
• 比较 11 和 12，因为 12 > 11，所以将 12 后移一位（也就是 arr[1] = arr[0]; 这步操作在代码里的体现）。
• 然后 j 变为 -1，跳出内层循环，把 key（也就是 11）插入到 arr[0] 的位置。

第二轮排序（插入 13）

• i = 2，key = 13，j = 1。
• 比较 13 和 12，发现 12 < 13，此时不需要移动元素，直接将 13 插入到 arr[2] 位置（也就是 arr[j + 1] = key; 的体现）。

第三轮排序（插入 5）

• i = 3，key = 5，j = 2。
• 比较 5 和 13，13 > 5，将 13 后移一位（arr[3] = arr[2]; ），j 变为 1。
• 再比较 5 和 12，12 > 5，将 12 后移一位（arr[2] = arr[1]; ），j 变为 0。
• 接着比较 5 和 11，11 > 5，将 11 后移一位（arr[1] = arr[0]; ），j 变为 -1。
• 最后把 5 插入到 arr[0] 位置（arr[j + 1] = key; ）。

第四轮排序（插入 6）

• i = 4，key = 6，j = 3。
• 比较 6 和 13，13 > 6，将 13 后移一位（arr[4] = arr[3]; ），j 变为 2。
• 比较 6 和 12，12 > 6，将 12 后移一位（arr[3] = arr[2]; ），j 变为 1。
• 比较 6 和 11，11 > 6，将 11 后移一位（arr[2] = arr[1]; ），j 变为 0。
• 比较 6 和 5，5 < 6，此时停止移动元素，将 6 插入到 arr[1] 位置（arr[j + 1] = key; ）。

最终经过这几轮排序后，数组变为有序的 {5, 6, 11, 12, 13}。

运行流程图解

假设输入数组为 {12, 11, 13, 5, 6}，排序过程如下：

最终结果

数组从 {12, 11, 13, 5, 6} 排序为 {5, 6, 11, 12, 13}。

优缺点

优点：

• 简单易实现，适合小规模数据。
• 稳定性好，能保持相同值的元素顺序。

缺点：

• 对大规模数据效率较低。
• 最坏情况下需要较多的比较和移动操作。