插入排序

2020-04-19

字数统计: 793字 | 阅读时长≈ 2分

简介

在中国，扑克牌是一种非常常见的棋牌游戏，通常人们整理手中已有牌的方法是一张一张来，将每一张牌擦混入到其他已经有序的牌中的适当位置。在排序算法中，有一种算法与整理牌的方式非常相似，那就是插入排序。

插入排序的主要原理是：假定当前索引左边的所有元素都是有序的，但是它们的最终位置还不确定，也许后面会有一些更小的元素会插入到它们之间，它们可能会移动，但是已经有序的元素之间相对顺序不会改变，当索引到达数组的最右端时，数组排序也就完成了。

具体分析

动图演示

strategy

算法实现与分析

先给出插入排序算法的一般实现：

public class Insertion{
	public static void sort(Comparable[] a){
		//将a[]按升序排列
		int N = a.length;
		//注意i是从1开始，因为默认左边元素有序，0的左边没有元素
		for(int i = 1; i < N; i++){
			//遍历有序的部分
			//如果a[j-1]>a[j],那么交换两者位置，然后从j-1继续向前遍历
			for(int j = i; j>0 && less(a[j],a[j-1]); j--){
				exch(a,j,j-1);
			}
		}
	}
}

从程序中可以看出，如果在每次循环中，都需要进行交换和比较，那么最坏情况，也就是倒序情况下需要 ~ (N^2)/2次比较和~ (N^2)/2次交换。
而最好情况下，也就是数组已经是所需要的有序状态，那么只需要 （N-1）次比较，0次交换
所以在平均情况下，插入排序需要 ~ (N^2)/4次比较和~ (N^2)/4次交换。

对于一般情况来说，数组是部分有序的，其中存在一部分倒置的情况。倒置指的是数组中的两个顺序颠倒的元素。
比如 EXAMPLE中共有11对倒置： E-A、X-1、X-M、X-P、X-L、X-E、M-L、M-E、P-L、P-E、L-E
根据上述插入排序算法的原理，我们可以看出来，每一次交换，都是将原本顺序不对的两个元素恢复顺序，也就相当于每一次交换都是去掉了一对倒置，因此得出结论：

插入排序需要的交换操作和数组中倒置的数量相同
需要的比较次数大于等于倒置的数量，因为比较之后未必需要交换。

对于上述程序的改进：
在上面程序中，每进行一次比较，如果出现倒置就进行一次交换，一般来说，进行一次交换需要访问3次数组，而如果选择先取出较小元素，然后较大元素向右移动，最后将较小元素填入到空出来的索引处，这样的方式能够很好的减少对数组的访问次数，从而提升插入排序的速度。

参考

本文作者： xczll
本文链接： https://xczllgit.github.io/2020/04/19/algorithm/2020-04-19-insertSort/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！