前言

排序是作为数据处理时最常用到的算法，也是基础算法的最基本的操作。常见的排序操作分为：插入排序、冒泡排序、选择排序、归并排序、快速排序、计数排序以及基数排序。

本篇博客介绍插入排序的思想和实现。

插入排序

????????插入排序，顾名思义，重点在于插入操作。其排序的方法就像我们在玩扑克牌时进行捋牌的操作。当我们面前有固定数量的牌时，我们会取出一张牌，把它拿到手里，然后继续抽牌，把它放到手上正确的位置，即插入到正确的位置，以此类推，知道把所有的牌都插入进来，完成排序操作。

????????反映到数组上，就相当于从前往后依次取出一个元素，然后插入到前面排好序的数据中。想到这，大概就有一些思路了。接下来我们把它具体一下。

????????对于一个数组Array[n]，n>1，我们可以用如下操作完成插入排序：

????????从第二个元素Array[1]开始，取出元素，然后将该元素与前面的元素进行比较，插入到相应的位置；然后取出第三个元素Array[2]，与前面排好的两个元素进行比较，插入正确位置；然后取出第四个元素…第五个元素……这样的操作直到最后一个元素也完成插入操作。

伪代码如下：

INSERTION-SORT(A){

? ? ? ? for j = 1?to?A.length - 1? ? ? ? ? ? ? ? ?//从第二个元素开始到最后一个元素

? ? ? ? ? ? ? ? key=A[ j ]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//取出要插入的元素

? ? ? ? ? ? ? ? i = j - 1

? ? ? ? ? ? ? ? while i > 0 and?A[ i ] > key

? ? ? ? ? ? ? ? ? ? ? ? A[ i + 1 ] = A[ i ]

? ? ? ? ? ? ? ? ? ? ? ? i = i - 1? ? ? ? ? ? ? ? ? ? ? ? ? ?//将比key大的元素后移，找到插入位置

? ? ? ? ? ? ? ? A[ i + 1 ] = key? ? ? ? ? ? ? ? ? ? ? ?//插入元素

}

?C/C++的实现如下：

void insertion_sort(int* a, int length) {   //参数：待排序数组，数组长度
	int i = 0, j = 0;
	int key;
	for (i = 1; i < length; i++) {          //从第二个数前往后遍历
		key = a[i];                         //取出目标数字
		j = i - 1;                          //找到前一项
		while (j >= 0 && a[j] > key) {      //从后往前遍历，并向后补位，直到找到比它小的项
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = key;                     //将取出的数字放在空出的正确位置
	}
	return;
}