插入排序（Insertion Sort）是一种简单直观的排序算法，其核心思想是将未排序的元素逐个插入已排序部分的合适位置，直到整个数组排序完成。它适用于小型数据集或是部分有序的数据集，并且相对于其他复杂度更高的算法，插入排序有较好的性能表现。

原理

        插入排序的基本思路类似于整理扑克牌的过程：将手中的牌逐一插入到已经有序的牌中的正确位置。具体来说，从第二个元素开始，依次将其插入到已排序部分中，直到所有元素都插入完成。

算法步骤

1. 初始已排序部分：将第一个元素视为已排序部分。
2. 逐个插入：遍历未排序部分的每个元素，在已排序部分中找到合适的位置并插入。
3. 重复直到完成：重复以上步骤，直到所有元素都插入到已排序部分。

动画演示

以下是插入排序的动画演示，有助于理解其工作原理：

#include <stdio.h>

// 插入排序函数
void insertion_sort(int arr[], int n) {
    int i, j, key;
    
    // 从第二个元素开始，将其插入到已排序部分的合适位置
    for (i = 1; i < n; i++) {
        key = arr[i]; // 当前要插入的元素
        j = i - 1;
        
        // 将大于key的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        // 插入key
        arr[j + 1] = key;
    }
}

// 测试插入排序的例子
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前的数组:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    // 调用插入排序函数
    insertion_sort(arr, n);
    
    printf("排序后的数组:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

特性与复杂度分析

• 时间复杂度：插入排序的时间复杂度为O(n^2)，因为在最坏情况下（逆序数组），需要进行n*(n-1)/2次比较和交换操作。最好情况：原数组有序。O(n)，比较次数：n-1，交换次数：0。
• 稳定性：插入排序是一种稳定的排序算法，相同元素的相对位置不会改变。
• 空间复杂度：插入排序是一种原地排序算法，它只需要常数级别的额外空间O(1)。

优化

虽然插入排序已经相对高效，但也可以通过一些优化来提升性能：

• 二分查找插入：在已排序部分中采用二分查找的方式找到插入位置，以减少比较次数。
• 希尔排序：希尔排序是插入排序的一种改进，通过比较较远的元素来交换不相邻的元素，以加快排序速度。