常用排序算法之插入排序

目录

前言

一、基本原理

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

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;
}

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

1. 时间复杂度

1.最优时间复杂度

        当数组已经有序时，每次插入只需比较一次，无需移动元素。

2.最差时间复杂度

        当数组为逆序时，每次插入都需要将所有已排序部分元素向右移动。

3.平均时间复杂度

        一般情况下，插入排序的性能表现介于最佳和最差之间。

2. 空间复杂度

        插入排序是原地排序算法，只需常数级别的额外空间，空间复杂度为O(1) 。

三、插入排序的优缺点

1.优点

1. 简单直观：算法易于理解和实现。

2. 适合小数据集：对于小规模数据排序性能较好。

3. 稳定性：插入排序是稳定排序算法，不会改变相同元素的相对位置。

4. 局部有序优化：当数据部分有序时，插入排序的性能非常接近线性时间。

2.缺点

1. 效率低下：对于大规模数据，插入排序的性能较差，时间复杂度较高。

2. 多次元素移动：在数组为逆序的情况下，插入排序需要频繁移动元素，效率较低。

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

1. 二分插入排序

• 改进点：在插入时，通过二分查找定位插入位置，从而减少比较次数。

• 时间复杂度：虽然查找位置优化为 ，但元素移动次数仍为 。

2. 希尔排序（Shell Sort）

• 基于插入排序的改进版，通过引入增量分组的思想，对远距离元素进行预排序，逐步缩小分组间隔，最终变为插入排序。

• 时间复杂度：最优可达 。

五、插入排序的应用场景

1. 小规模数据排序：在数据量较小时，插入排序简单易用，且性能尚可。

2. 近乎有序数据：插入排序在处理已部分有序的数据时表现优异。

3. 作为复杂排序的辅助算法：如快速排序或希尔排序中，用插入排序优化小数组的排序效率。

六、总结

        插入排序是一种经典的排序算法，以其简单性和直观性被广泛应用于教学和小规模排序场景中。虽然它在大数据排序上的性能较差，但通过改进（如二分插入排序）或结合其他算法（如希尔排序），可以显著提升效率。