插入排序

简介

插入排序的扑克牌演示

插入排序的循环过程和冒泡排序，选择排序不同，不是每次处理元素的时候确定该元素的最终位置，插入排序是从前到后依次处理每个位置的数据，而处理该位置时，之前的数据都是已经排好序的，把这个数据插入到前面排好序的元素中的正确位置，和我们玩扑克牌的过程类似。

插入排序每次处理数字的时候，前面的问题已经是排好序的，也就是前面已经构成了子序列的解，此类可以拆分成子问题的问题通常可以用递归等方式实现。

插入排序过程从第二个元素开始遍历，第二个元素和第一个元素比较大小，如果比第一个数字小，则插入到第一个元素的前面。

之后处理第三个元素，因为前两个元素比较排好顺序，所以可以确定第三个元素和前两个元素的大小关系，之后将第三个元素插入到正确的位置。

依次类推，完成整个排序过程。

流程

• 从第二个数据开始循环，直到最后一个元素。
  • 将该元素和之前的元素进行比较，因为之前的元素都是排序的，所以确认该元素的位置之后，将该元素插入到合适的位置。
  • 在完成插入之后，该位置以及之前的数据都已经排序完成。

实现

void InsertionSort(int *a, int len)
{
	for (int j=1; j<len; j++)
	{
		int key = a[j];
		int i = j-1;
		while (i>=0 && a[i]>key)
		{
			a[i+1] = a[i];
			i--;
		}
		a[i+1] = key;
	}
}