雅乐网

插入排序是一种简单排序。对于少量元素的排序它很有效。

插入排序的工作方式类似于玩扑克牌抓牌时的排序

此图出自算法导论2.1中插入排序插图

开始的时候左手为空，每次从桌子上拿走一张牌并把它插入到左手中正确的位置。可以从右到左依次比较。拿在左手上的牌总是有序的。

c++实现

#include <cstdio>
#include <cstdlib>
#include <ctime>

template <typename T>
void insertSort(T a[], const int n)
{
	for (int i = 1; i < n; ++i)
	{
		int tmp = a[i];
		int j;
		for (j = i-1; j >= 0 && a[j] > tmp; --j)
			a[j+1] = a[j];
		a[j+1] = tmp;
	}
}

int main()
{
	const int N = 100;
	int a[N];
	int i;
	srand((int)time(0));	//生成随机数组
	for (i = 0; i < N; i++)
		a[i] = rand() % N;


	for (i = 0; i < N; ++i)
		printf("%d ", a[i]);

	insertSort(a, N);
	putchar('\n');

	for (i = 0; i < 100; ++i)
		printf("%d ", a[i]);

	return 0;
}

正确性

下标j表示的是“当前牌”。在for循环的每次迭代开始 a[0]到a[j-1]的子数组构成了当前“左手上排序好的牌”。它总是有序的。我们把它称为循环不变式。

循环不变式可以用来证明算法的正确性。主要性质有

1.初始化：循环的第一次迭代之前，它为真。

2.保持：如果某次迭代之前它为真，那么下次迭代之前它仍然为真。

3.终止： 循环终止时，不变式帮助我们证明正确性。

下面看看插入排序

template <typename T>
void insertSort(T a[], const int n)
{
	for (int i = 1; i < n; ++i)
	{
		int tmp = a[i];
		int j;
		for (j = i-1; j >= 0 && a[j] > tmp; --j)
			a[j+1] = a[j];
		a[j+1] = tmp;
	}
}

在算法执行的过程中，a[0]到a[i-1]始终是有序的。

1.初始化：在第一次迭代时，i等于1，a[o]到a[i-1]只包含a[0]，是有序的。这表明第一次迭代之前循环不变式成立。

2.保持：第8行的for循环体将a[i]插入到合适的位置，以使a[0]到a[i]有序。

3.终止： for循环终止的时候i = n 。因此a[0]到a[n-1]的数组已经有序。

复杂度

在最糟糕的情况下，也就是序列逆序排列时，对于n-1个数中第x个数，每次将该数插入时将引起x-1次数组移动（这里不计算比较时间）,求和得到 n(n-1)/2，很明显时间复杂度为O(n²)。

在已经排好序的情况下，时间复杂度为O(n)。