插入排序

代码

C语言代码：

#include <stdio.h>

void insertion_sort(int arr[], int n) {
    int i, j, key;
    for (i = 2; i <= n; i++) {  // 从第二个元素开始
        key = arr[i];
        for (j = i - 1; arr[j] > key; j--) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {-1000000, 12, 11, 13, 5, 6};  // 使用一个非常小的值作为哨兵，第一个元素不会被排序
    int n = sizeof(arr)/sizeof(arr[0]) - 1;  // 计算有效长度（去掉哨兵）
    
    insertion_sort(arr, n);

    printf("Sorted array: ");
    for (int i = 1; i <= n; i++) {  // 从第一个实际元素开始打印
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

代码解释

1. 初始化：数组 arr 的第一个元素 -1000000 作为哨兵，用于边界检查。排序部分从第二个元素开始。
2. 主排序循环：
   • 从第二个元素（即下标为2）开始遍历，每次将当前元素存入 key。
   • 内部 for 循环从当前元素的前一个位置开始向前遍历，如果当前元素比 key 大，则将其向后移动一位，直到找到合适位置插入 key。
3. 结果输出：排序完成后，输出排序后的数组，忽略第一个哨兵元素。

示例运行

假设输入数组为 {-1000000, 12, 11, 13, 5, 6}：

1. 初始状态：{-1000000, 12, 11, 13, 5, 6}
2. 插入 11：{-1000000, 11, 12, 13, 5, 6}
3. 插入 13：{-1000000, 11, 12, 13, 5, 6}
4. 插入 5： {-1000000, 5, 11, 12, 13, 6}
5. 插入 6： {-1000000, 5, 6, 11, 12, 13}

最终结果：{5, 6, 11, 12, 13}

时间复杂度分析

插入排序的时间复杂度主要取决于数组的初始顺序。

• 最优时间复杂度：当输入数组已经有序时，插入排序只需要进行 $O(n)$ 次比较，时间复杂度为 $O(n)$。
• 最坏时间复杂度：当输入数组是逆序时，插入排序需要进行最多的比较和移动操作，时间复杂度为 $O(n^2)$。
• 平均时间复杂度：插入排序在一般情况下的时间复杂度为 $O(n^2)$。

空间复杂度分析

插入排序是一种原地排序算法，不需要额外的辅助空间，空间复杂度为 $O(1)$。在本实现中，我们仅使用了几个额外的变量（i, j, key），因此空间复杂度保持为常数级别。

优缺点

优点：

• 简单易实现。
• 对于小规模数据集表现良好。
• 稳定排序算法，不改变相同元素的相对顺序。
• 原地排序，空间复杂度低。

缺点：

• 对于大规模数据集，时间复杂度较高，不适合处理大量数据。

适用场景

插入排序适用于以下场景：

• 数据量较小的排序。
• 数组已经部分有序时，插入排序效率较高。
• 需要一个简单且稳定的排序算法时。

总结

插入排序是一种简单直观的排序算法，尽管其最坏情况下时间复杂度较高，但在特定场景下仍然具有优势，特别是对于小规模或部分有序的数据集。使用哨兵元素可以减少边界检查，提高算法的效率。