本文共 878 字，大约阅读时间需要 2 分钟。

插入排序（Insertion Sort）

插入排序是一种基本的排序算法，通过对元素一个一个地插入到已排序的位置来实现对整体数组的排序。这种方法的核心思想是，每次将一个未排序的元素插入到已排序的子数组中，直到所有元素都被插入完成。

插入排序的实现步骤如下：

以下是插入排序的代码示例：

#include 
   
    
void insertionSort(int a[], int size) {
    int i, j, temp;
    for (i = 0; i < size; i++) {
        for (j = size - 1; j > i; j--) {
            if (a[j] > a[j - 1]) {
                temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
            }
        }
    }
}
int main() {
    int a[1000], n, i;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        a[i] = i + 1;
    }
    insertionSort(a, n);
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}
   

插入排序的时间复杂度为O(n²)，空间复杂度为O(1)，适用于数据范围较小且需要频繁排序的场景。

插入排序的优化思路在于减少元素比较次数，可以通过三分法或其他优化技术将时间复杂度降低至O(n log n)。

转载地址：http://tnzpz.baihongyu.com/