vlambda博客
学习文章列表

排序算法是算法领域十分经典的一类算法，它的名字通俗易懂：给数字排序，让一组无序的数据通过排序算法后，能增序或者降序地输出。

      排序算法有很多种，本文来详细讲讲 "插入排序法"。

（本文均是增序排序，降序排序同理即略）

其实插入排序法很好理解，就像打牌时整理手上一堆无序的牌：将待排序的牌一一插入已排序中的合适位置。

如下图，就是将待排序的 7 插入已排序的 2 4 5 10的牌堆中。

如下图，1 7 8 13是已经排序好的部分，取出未排序的6，将其插入已排序的堆中。

需要先找到插入位置，再将插入位置之后的元素都向后移动一格，然后就能插入6了。

按照上面的方法，初始时所有的数字只有第一个是已排序的，后面均视为未排序部分。将未排序的数字一一插入已排序的合适位置，即完成了插入排序。

我们将待排序的 n 个数字均存在数组中，数组从下标 0 开始到 n - 1 结束。

🔺 排序 n 个数字需要 n - 1次插入

      第 i 次的过程：需要插入元素 temp = a[i]，待插入位置 t = i

（此时数组内 0 ~ i-1 是已排序部分、i ~ n-1是未排序部分）

           🌂从 t 开始往前寻找合适的插入位置

                   ▲temp 比 a[t-1] 小：

                     a[t-1]后移一位

                      从 t - 1开始往前寻找合适的插入位置

                   ▲temp 不比 a[t-1] 小：

                       temp插入数组下标 t 内

下面看一个具体的例子来理解算法

将 "4 5 6 3 2 1" 增序排序，图中红色部分为已排序部分、黄色部分为未排序部分。

 下面是插入排序函数，亲测无误：

/* 增序的插入排序 * 传入：待排序数组a、数组元素个数n */void insertSort(int a[], int n) {  for (int i = 1; i < n; i++) { int temp = a[i]; //取出待插入元素 int t = i; //待插入的位置  /* 当待插入元素 小于 待插入位置的前一个元素 */ while(t >0 && temp < a[t - 1] ) { a[t] = a[t -1]; //将前一个元素后移 t--; //待插入位置前移 }  a[t] = temp; //插入合适位置 }}

奉上完整代码

//// Created by LittleCat on 2020/2/11.//#include <cstdio> /* 增序的插入排序 * 传入：待排序数组a、数组元素个数n */void insertSort(int a[], int n) {  for (int i = 1; i < n; i++) { int temp = a[i]; //取出待插入元素 int t = i; //待插入的位置  /* 当待插入元素 小于 待插入位置的前一个元素 */ while(t >0 && temp < a[t - 1] ) { a[t] = a[t -1]; //将前一个元素后移 t--; //待插入位置前移 }  a[t] = temp; //插入合适位置 }} int main() { int a[] = {5, 2, 3, 4, 15, 16, 100, 23, 88}; insertSort(a, 9);  for (int i = 0; i < 9; i++) printf("%d ", a[i]); //输出结果：2 3 4 5 15 16 23 88 100}

插入排序比较容易理解，可以看到有两个循环的嵌套，平均时间复杂度是 。最好的情况下（当待排序的数字串全是有序的），时间复杂度是O(1)，最坏的情况也就是一般情况: 。效率其实还是比较低的。

其比较适用的情况是：小规模数据 / 数据基本有序时。

再看一篇