插入排序

在这里插入图片描述

插入排序

百度百科上面有一个不错的例子是这样描述插入排序的，插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。这样，拿在左手上的牌总是排序好的。

用一个动态图演示插入排序过程：

在这里插入图片描述

首先把数组第一个元素a[0]看作是一个有序数列，然后a[1]开始与a[0]做比较，发现10比7大，那么a[1]的值需要插入在a[0]的前面，表示下来就是a[0]的值往后移到a[1]，然后a[1]的值移向a[0]，然后再拿a[2]与之前的有序数列a[0]，a[1]做比较，发现12大于10和7，那么原来的a[0]的值和a[1]的值，继续向右移动一个单位，把a[2]的值插入a[0]，如此，a[0]，a[1]，a[2]就是一个有序数列，如此往复，直到之后排序完成。

插入排序原理

1、将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；

2、取出下一个元素，在已经排序的元素序列中从后向前扫描；

3、如果该元素（已排序）大于新元素，将该元素移到下一位置；

4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

5、将新元素插入到该位置后；

6、重复步骤2~5。

代码

	int arr[] = { 1,5,69,8,10 };
	int j;
	for (int i = 1; i < 5; i++)
	{
		int temp = arr[i];
		for (j = i - 1;j >= 0 && arr[j] < temp;j--)
		{
			arr[j + 1] = arr[j];
		}
		 arr[j+1]= temp;
	}