插入排序

算法描述

插入排序是一种简单而直观的排序算法，它的思想是将数组分为已排序和未排序两部分，初始时已排序部分只包含数组的第一个元素，然后逐步将未排序部分的元素插入到已排序部分的正确位置，直到整个数组排序完成。

下面是插入排序算法的自然语言描述：

从数组的第二个元素开始，将其视为当前要插入的元素。
将当前元素与已排序部分的元素进行比较，从最右边的已排序元素开始。
如果当前元素小于已排序元素，则将已排序元素向右移动一个位置，为当前元素腾出空位。
继续比较当前元素与下一个已排序元素，直到找到一个已排序元素小于或等于当前元素，或者已经到达已排序部分的起始位置。
将当前元素插入到找到的位置，即将其赋值给该位置，并将已排序部分的元素向右移动一个位置。
重复步骤 2~5，直到将所有未排序元素插入到已排序部分。
最终得到一个完全有序的数组。

插入排序的时间复杂度为 $O(n^2)$ ，其中 $n$ 是数组的长度。尽管插入排序的效率相对较低，但对于小规模的数据集合或部分有序的数组，它仍然是一个简单且有效的排序算法。它的优点是在原地排序，不需要额外的存储空间，并且对于部分有序的数组，插入排序的性能较好。

编程实现

下面是用 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;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("排序后的数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

在上面的代码中，insertionSort 函数实现了插入排序算法。它从数组的第二个元素开始，将当前元素与前面已排序的元素进行比较，如果前面的元素较大，则将其向后移动，直到找到合适的位置插入当前元素。

在 main 函数中，我们定义了一个整数数组 arr，并计算出数组的长度 n。然后，我们调用 insertionSort 函数对数组进行排序。最后，我们使用循环打印排序后的数组。

运行该程序，输出将是排序后的数组：

排序后的数组：
11 12 22 25 34 64 90

这就是用 C 语言实现插入排序的简单示例。插入排序是一种简单且稳定的排序算法，适用于小规模的数据集合或部分有序的数组。对于大规模的数据集合，更高效的排序算法如快速排序或归并排序更为常用。

插入排序

算法描述​

编程实现​

算法描述

编程实现