深入浅出理解排序算法系列(2) 插入排序算法的实现与性能分析

vlambda
2021-01-15

深入浅出理解排序算法系列(2) 插入排序算法的实现与性能分析

概述：

插入排序的基本原理是在有序序列中插入一个元素，保持序列有序。

也就是说每次将一个待排序的元素，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

本文具体为大家讲解插入排序的2 种具体实现方法：

· 直接插入排序（Straight Insert Sort）

· 二分插入排序 (Bisection Insert Sort)

本系列的文章包含：

插入排序算法的实现与性能分析
交换排序算法的实现与性能分析
选择排序算法的实现与性能分析
归并排序算法的实现与性能分析
基数排序算法的实现与性能分析
总结：各种内部排序方法的比较

（注：先列出框架，后续不断更新中；本系列文章的算法实现全都基于Java语言，掌握其算法核心原理后使用任何语言都是可以的）

1. 插入排序的分类

现实生活中，当玩扑克牌游戏的时候，将新取的牌插入到已有序排列的牌中，这就是插入排序。我们根据插入位置的不同，以图示为大家做说明。

深入浅出理解排序算法系列(2) 插入排序算法的实现与性能分析

常见的插入排序主要有两种：直接插入排序和希尔排序。为帮助小伙伴们进一步学习解插入排序，本文在直接插入排序的基础上补充二分插入排序。

深入浅出理解排序算法系列(2) 插入排序算法的实现与性能分析

2. 直接插入排序算法

2.1 算法实现方法

直接插入排序的要求是假设待排序的元素存放在数组arary[0..n-1]中，开始时候先将第0个记录组成一个有序的子表，然后依次将后续的记录插入到这个有序子表中去，并且保持子表的有序性。

具体步骤如下：

· 将array[i]暂存在临时变量temp中；

· 将temp与array[j](j=i-1,i-2,...,0)依次比较，当temp<array[j]时，将array[j]后移一位，直到temp>=array[j]为止（此时j+1即为array[i]插入的位置）；

· 将temp插入到j+1的位置上；

· 令i=1,2,3...,n-1,重复上述前三步骤；

我们以Array[12,15,9,20,6,31,24]为例实现简单插入排序，排序过程如下图：

深入浅出理解排序算法系列(2) 插入排序算法的实现与性能分析

/** * 直接插入排序算法示例 * @param array * @return */public int[] StraightInsertSort(int[] array) { int i, j, temp; for (i = 1; i < array.length; i++) { //n-1次扫描 temp = array[i]; //定义临时变量，将待插入的第i个元素暂存在temp中 for (j = i - 1; j >= 0 && temp < array[j]; j--) { array[j + 1] = array[j]; //把前面比array[i]大的元素往后移动 }  array[j + 1] = temp;//当temp>=array[j]的时候，此时将array[i]插入到第j+1的位置上 } return array;}

【思考】

以上算法实现了简单插入排序，我们用“j>=0”用来控制下表越界，但这并不是极好的写法，因为每次循环都需要多做一步的条件判断，显然排序效率不高，因此我们可以通过添加监视哨的方法做优化。原理如下：

· 将待排序的N个元素从下标为1的存储单元开始依次存放在数组array中；

· 将array[0]设置为一个“监听哨”，在查找之前先将array[i]赋值给array[0]，每循环一次只需要进行元素的比较，不需要关心下标是否越界；

· 当比较到第0个位置的时候，array[0]==array[i]是肯定成立的，所以结束循环。由于通过设置“监听哨”，只需要一个循环判断条件就OK了，这将提高算法运行的效率。

具体代码实现如下：

/** * 直接插入排序算法优化（加上监视哨，减少循环判断，提高算法效率） * @param array * @return */public int[] StraightInsertSort(int[] array) { int i, j; for (i = 1; i < array.length; i++) { //n-1次扫描 array[0] = array[i]; //将待插入的第i个元素暂存在array[0]中 for (j = i - 1; array[0] < array[j]; j--){ array[j + 1] = array[j]; //把前面比array[i]大的元素往后移动 } array[j + 1] = array[0]; //当array[0]>=array[j]的时候，此时将array[i]插入到第j+1的位置上 } return array;}

【注意】

使用array[0]作为监听哨之后，具有N个存储单元的顺序表只能存放N-1个元素，因此注意顺序表的存储长度。

2.2 算法性能分析

空间复杂度：仅用了一个辅助单元，空间复杂度为O(1)；
时间复杂度：根据插入array[i]时元素比较的次数Ci和移动次数Mi的最大值、最小值、平均值来计算；

深入浅出理解排序算法系列(2) 插入排序算法的实现与性能分析

3. 算法稳定性：稳定；

【思考】

从直接插入排序算法的时间复杂度上，其实可以看出，当原始数据越接近有序，排序速度越快，在最坏情况下待排序序列按照关键词逆序排列，时间复杂度为O(n^2),平均情况下算法复杂度仍为O(n^2)。所以为了提高排序速度，我们要

· 减少元素的比较次数

· 减少元素的移动次数

如何优化算法呢？考虑个问题，当直接插入排序时候循环遍历有序序列，顺序查找待插入元素array[i]的插入位置，这个顺序查找的过程是否可以优化呢？答案是可以的，我们可以使用二分插入算法！

3. 二分插入排序算法

二分插入排序使用到二分法思想，如果对此不了解小伙伴可熟悉此知识点（在此分享一篇相对不错的博客《二分查找各种情况大总结》，供大家参考）

3.1 算法实现方法

深入浅出理解排序算法系列(2) 插入排序算法的实现与性能分析

如上图，给定一个待排序序列array数组，将array[4]位置上的元素7插入到前段的有序序列中，现将array[4]的值存入临时变量temp中，设置left、right指针，left指针从下标0开始向右移动，right指针从下标i-1开始向左移动，循环比较中值与待插入元素7的大小，从而确定array[i]的插入位置。

/** * 二分插入排序算法示例 * @param array * @return */public int[] BisectionInsertSort(int[] array) { int i, j, left, right, mid, temp; for (i = 1; i < array.length; i++) { temp = array[i]; //临时存储待插入元素array[i] left = 0; right = i - 1; //设置查找段的起点和终点 while (left <= right) { //二分定位 mid = (left + right) / 2; if (temp < array[mid]) right = mid - 1; else left = mid + 1; } for (j = i - 1; j >= left; j--) array[j + 1] = array[j]; //元素右移 array[left] = temp; //此时，left指针的位置就是array[i]要插入的位置，插入结束 } return array;}