C语言insertsort函数如何实现高效插入排序？-C语言-盈思创科技

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

（图片来源网络，侵删）

算法核心思想

插入排序的核心思想可以类比我们整理扑克牌：

初始状态：你手中只有一张牌，它本身就是有序的。
取下一张牌：从牌堆中取出下一张牌。
插入到正确位置：将这张牌与你手中的牌从右到左进行比较，如果它比某张牌小，就将那张牌向右移一位，直到找到它应该插入的位置，然后将它放进去。
重复：重复上述过程，直到所有牌都在手中且有序。

在数组中,这个过程是这样的：

我们将数组分为两个部分：已排序区和未排序区。
初始时,arr[0] 就是已排序区，剩下的 arr[1...n-1] 是未排序区。
每次从未排序区的第一个元素（arr[i]）取出，将其与已排序区的元素从后向前（arr[i-1], arr[i-2], ...）逐一比较。
arr[j]（已排序区元素）大于 arr[i]（待插入元素），就将 arr[j] 向后移动一位。
当找到 arr[j] <= arr[i] 的位置时，arr[i] 就应该插入到 j+1 这个位置。

C 语言实现

下面是一个完整的、带有详细注释的 C 语言插入排序函数实现。

#include <stdio.h>
/**
 * @brief 插入排序函数
 * @param arr 待排序的整型数组
 * @param n 数组的元素个数
 */
void insertionSort(int arr[], int n) {
    int i, j, key;
    // 外层循环，从第二个元素开始，逐个将未排序区的元素插入到已排序区
    // i 代表当前要插入的元素的索引
    for (i = 1; i < n; i++) {
        // key 是我们当前要插入的元素，先把它存起来
        // 因为在后面的移动过程中，这个位置的值可能会被覆盖
        key = arr[i];
        // j 是已排序区最后一个元素的索引
        // 内层循环，在已排序区从后向前扫描，寻找 key 的正确插入位置
        j = i - 1;
        // 将所有大于 key 的元素向后移动一位
        // 1. j >= 0 确保我们不会越界访问数组
        // 2. arr[j] > key 表示 key 还应该继续向前找位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // 将较大的元素向后移动
            j--; // 继续向前比较
        }
        // 循环结束后，j + 1 key 的正确插入位置
        // 因为当 arr[j] <= key 时，循环停止，key 应该在 j+1
        // 或者 j < 0 时，key 应该在数组的第一个位置 (j+1 = 0)
        arr[j + 1] = key;
    }
}
// --- 辅助函数：打印数组 ---
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
// --- 主函数：用于测试 ---
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原始数组: \n");
    printArray(arr, n);
    insertionSort(arr, n);
    printf("排序后数组: \n");
    printArray(arr, n);
    // 测试一个已经有序的数组
    int arr2[] = {1, 2, 3, 4, 5};
    n = sizeof(arr2) / sizeof(arr2[0]);
    printf("\n原始有序数组: \n");
    printArray(arr2, n);
    insertionSort(arr2, n);
    printf("排序后数组: \n");
    printArray(arr2, n);
    // 测试一个逆序数组
    int arr3[] = {5, 4, 3, 2, 1};
    n = sizeof(arr3) / sizeof(arr3[0]);
    printf("\n原始逆序数组: \n");
    printArray(arr3, n);
    insertionSort(arr3, n);
    printf("排序后数组: \n");
    printArray(arr3, n);
    return 0;
}

代码分步解析

for (i = 1; i < n; i++)
（图片来源网络，侵删）
- 这是外层循环,它控制着插入的“轮数”。
- i 从 1 开始，因为我们默认第一个元素 arr[0] 是已经排好序的。
- 每一轮循环,我们都处理 arr[i] 这个元素，将其插入到 arr[0...i-1] 这个已排序的子数组中。
key = arr[i]
- key 是一个临时变量，用来存储当前要插入的元素的值。
- 这是非常关键的一步,因为在 while 循环中，我们需要将 arr[j] (比 key 大的元素) 向后移动，即 arr[j+1] = arr[j]，如果我们不提前保存 arr[i] 的值，它就会被 arr[j] 的值覆盖掉，导致数据丢失。
j = i - 1;
- j 指向已排序区域的最后一个元素，我们从这里开始，向前寻找 key 的插入位置。
while (j >= 0 && arr[j] > key)
- 这是内层循环,负责“寻找位置和移动元素”。
- j >= 0：确保我们的索引不会变成负数，防止数组越界，当 j 变为 -1 时，意味着 key 比已排序区所有元素都小，应该放到数组的第一个位置。
- arr[j] > key：这是比较的核心，如果已排序区的元素 arr[j] 比 key 大，说明 key 还不能放在这里，需要继续向前找，我们将 arr[j] 向后移动到 arr[j+1] 的位置。
arr[j + 1] = key;
（图片来源网络，侵删）
- 当 while 循环结束时，意味着我们已经找到了 key 的正确位置。
- 为什么是 j + 1？
  - 情况一：循环因为 arr[j] <= key 而停止。key 应该插入在 arr[j] 的后面，也就是 j+1 的位置。
  - 情况二：循环因为 j < 0 而停止，这意味着 key 比所有已排序元素都小，应该放在索引 0 的位置。j 是 -1，j + 1 正好是 0。

算法分析

时间复杂度:
- 最好情况: O(n)，当输入数组已经是升序排列时，内层 while 循环每次只比较一次 (arr[j] > key 为假) 就会退出，外层循环执行 n-1 次，所以总操作次数是线性的。
- 最坏情况: O(n²)，当输入数组是降序排列时，对于每个 arr[i]，内层 while 循环都需要比较并移动 i 次，总操作次数是 1 + 2 + 3 + ... + (n-1) = n(n-1)/2，是平方级的。
- 平均情况: O(n²)，对于随机排列的数组，平均时间复杂度也是平方级的。
空间复杂度: O(1)。
- 插入排序是原地排序算法，它不需要额外的存储空间，只使用了常数个额外变量（如 i, j, key）。
稳定性: 稳定。
- 如果数组中有相等的元素（5_a, 3, 5_b, 1），排序后它们的相对位置不会改变，在比较时，只有 arr[j] > key 时才会移动，arr[j] == key 时不会移动，5_a 和 5_b 的原始顺序得以保留。

优缺点总结

优点:

实现简单：代码逻辑直观易懂。
空间效率高：是原地排序，空间复杂度为 O(1)。
对小规模数据高效：对于元素数量很少的数组（n < 20），插入排序通常比更复杂的算法（如快速排序、归并排序）更快，因为它的常数因子很小。
对近乎有序的数据表现优异：如果输入数据基本有序，插入排序接近 O(n) 的时间复杂度，非常高效。

缺点:

时间复杂度高：对于大规模数据，O(n²) 的时间复杂度使得它非常慢，远不如 O(n log n) 的算法。
不是自适应的：虽然对近乎有序的数据好，但它的最坏和平均情况都是 O(n²)，无法从根本上优化。

应用场景

由于其简单和在小数据集上的高效性,插入排序常被用作更复杂排序算法（如 Timsort，Python 的内置排序算法）的一部分，用于处理小规模的子数组。

C语言insertsort函数如何实现高效插入排序？