----- ——————插入排序——————--------

插入排序（Insertion Sort）

插入排序是一种简单的排序算法，适用于小型数据集或几乎已经排序好的数据。它的基本思想是将数据分为已排序部分和未排序部分，通过不断将未排序部分的元素插入到已排序部分中，从而实现整个数据的排序。插入排序在平均情况下和最坏情况下的时间复杂度为O(n²)，在最佳情况下（数据已接近排序好）时间复杂度为O(n)，空间复杂度为O(1)。

插入排序的工作原理

1. 初始状态：

   • 将待排序数组分为已排序部分和未排序部分。开始时，已排序部分只包含数组的第一个元素，未排序部分包含剩余的元素。

2. 插入元素：

   • 从未排序部分中取出一个元素（称为key），将其插入到已排序部分的正确位置。

3. 移动元素：

   • 将已排序部分中比key大的元素向后移动一个位置，为key腾出空间。

4. 插入key：

   • 将key插入到腾出的空间中。

5. 重复过程：

   • 继续取出未排序部分的下一个元素，并重复上述步骤，直到所有元素都被插入到已排序部分中。

插入排序的实现（C语言示例）

以下是插入排序在C语言中的实现示例：

c
复制代码
#include <stdio.h>

// 插入排序函数
void insertionSort(int arr[], int n) {
    int i, key, j;
    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 = j - 1;
        }
        // 将key插入到正确的位置
        arr[j + 1] = key;
    }
}

// 打印数组函数
void printArray(int arr[], int size) {
    int i;
    for (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);
    return 0;
}

插入排序的优缺点

优点：

• 实现简单，容易理解。
• 对于小规模数据或近乎已排序的数据，效率较高。
• 稳定排序：相同元素的相对顺序不会被改变。

缺点：

• 时间复杂度为O(n²)，对于大规模数据，效率较低。
• 不适合处理大型数据集。

插入排序的应用场景

• 小规模数据：插入排序适合处理数据量较小的场景，如小型数据库的排序。
• 部分排序数据：当数据接近排序好时，插入排序能高效地完成排序。
• 在线排序：插入排序能在数据流中实时插入新数据并保持排序。

总结

插入排序是一种简单但有效的排序算法，适合处理小规模或部分已排序的数据。其基本思想是通过将未排序部分的元素逐个插入到已排序部分的正确位置，实现整个数据的排序。虽然在处理大规模数据时效率较低，但它的实现简单且稳定，适用于特定场景的排序需求。