当前位置：首页 > article >正文

常用排序算法之插入排序

article 2025/1/22 13:11:36

前言

一、基本原理

1.算法步骤

2.动画演示

3.插入排序的实现代码

二、插入排序的时间复杂度

1. 时间复杂度

1.最优时间复杂度

2.最差时间复杂度

3.平均时间复杂度

2. 空间复杂度

三、插入排序的优缺点

1.优点

2.缺点

四、插入排序的改进与变种

五、插入排序的应用场景

六、总结

前言

插入排序（Insertion Sort）是一种简单且直观的排序算法，常用于小规模数据的排序或作为其他复杂排序算法的一部分（如快速排序的小数组优化）。

本文将详细介绍插入排序的基本原理、实现代码、时间复杂度及其适用场景，帮助你轻松掌握这一算法。

一、基本原理

插入排序的核心思想是将数组分为已排序部分和未排序部分。通过逐一从未排序部分取出元素，将其插入到已排序部分的合适位置，最终完成排序。

1.算法步骤

1. 从数组的第二个元素开始，视为当前需要插入的元素。

2. 从已排序部分的最后一个元素开始比较，如果当前元素较小，则将已排序部分元素向右移动。

3. 重复上述步骤，直到找到插入位置，将当前元素插入。

4. 对剩余的未排序部分重复以上步骤，直至整个数组有序。

2.动画演示

这里我写了一个程序用来演示直接插入算法的过程。

假如我要进行排序的数据元素分别为5，3，, 8，6，2，7，4，1。

初始的时候，我们已排序中的部分中的数据元素使用绿色表示，未排序的使用蓝色表示。

图1.初始状态

初始状态下，我们把第一个数据元素看做一个已经排列好的部分。

同时把第二个数据元素作为下次要插入的数据元素。

图2.插入排序的动画演示

我们以上面的数组为例看一下具体的过程：

5，3, 8，6，2，7，4，1

1.第一轮

首先确定5是已经排列好的，我们将3进行插入操作。将3插入到仅有一个数据元素为5的数组中，显然5比3大，我们将3插入到5的前面。至此第一轮插入结束。此时的数组为{3,5,8,6,2,7,4,1}。

2.第二轮

在上一轮中，已排序的区间为{3,5},现在我们将8拿出来和前面排列好的部分进行比较。因为5<8,依次已排序区间应该为{3,5,8}。第二轮结束，此时排序依然是{3,5,8,6,2,7,4,1}。

2.第二轮

3.第三轮

在上一轮中，已排序的区间为{3,5,8},现在我们将6拿出来和前面排列好的部分进行比较。因为8>6,我们在把6和前面的一个数据元素5比较，5<6，把6查到5后面,依次已排序区间应该为{3,5,6，8}。第二轮结束，此时排序依是{3,5,6,8,2,7,4,1}。

4.第四轮

在上一轮中，已排序的区间为{3,5,6,8},现在我们将2拿出来和前面排列好的部分进行比较。具体的比较过程和上一轮相同，这里不重复了，此时排序是{2,3,5,6,8,7,4,1}。

5.第五轮

在上一轮中，已排序的区间为{2,3,5,6,8},现在我们将7拿出来和前面排列好的部分进行比较。具体的比较过程和上一轮相同，这里不重复了，此时排序是{2,3,5,6,7,8,4,1}。

3.第六轮

在上一轮中，已排序的区间为{2,3,5,6,7,8},现在我们将4拿出来和前面排列好的部分进行比较。具体的比较过程和上一轮相同，这里不重复了，此时排序是{2,3,4,5,6,7,8,1}。

3.第三轮

在上一轮中，已排序的区间为{2,3,4,5,6,7,8},现在我们将1拿出来和前面排列好的部分进行比较。具体的比较过程和上一轮相同，这里不重复了，此时排序是{1,2,3,4,5,6,7,8}

3.插入排序的实现代码

以下是插入排序的 C语言实现：

#include <stdio.h>
// 插入排序函数
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // 当前要插入的元素
        int j = i - 1;

        // 将比 key 大的元素向右移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // 插入 key 到正确的位置
        arr[j + 1] = key;

        // 打印当前排序步骤
        printf("第 %d 步: ", i);
        for (int k = 0; k < n; k++) {
            printf("%d ", arr[k]);
        }
        printf("\n");
    }
}
int main(int argc, const char * argv[]) {
    int arr[] = {5, 3, 8, 6, 2, 7, 4, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // 执行插入排序
    insertionSort(arr, n);

    // 打印排序后的数组
    printf("排序后数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    
    return 0;
}