排序：插入排序

1. 插入排序简单介绍：有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法–插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)，该排序是稳定的。
2. 实现思路分析：插入排序有点像我们平时打扑克一样，那一张牌，往里里面插入，每次插入的时候，手里的牌已经是有序的，但在实现的时候，我们不是一个数据一个数据插入，而是直接拿到整个数组，就向拿到整个牌一样，所以，我们就这样来转化，把整个数组分为一个有序数组和除有序数组的外的无须数组，即整个数组 = 有序数组 + 无序数组。我们用一个下标指向有序数组的最后一个元素，通过下标加一找到要插入的元素，然后用临时变量来保存要插入的元素，然后用要插入的元素和有序数组的元素比较（从有序数组的最后一个元素向前一次比较），如果比要插入元素大，就要向右依次挪动有序数组的元素，然后插入临时变量中保存的要插入的元素。这是一次的插入排序，然后循环，然后让指向有序数组最后一个元素的下标加一，知道该下标指向数组的倒数第二个元素时，循环结束。
   

从上图我们也可以看出，在最坏的情况的下，其每次的操作次数为，挪动数据的次数+插入数据，时间复杂度(（1+2+3…+n)*n)/2,为O(N^2).

int arr = {5,4,3,2,1};
void InsertSort(int* arr, int n)
{
	int end  = 0;
	int tmp = 0;
	int i = 0;
	assert(arr);

	for(i=0; i<n-1; i++)
	{
		end = i;
		tmp = arr[end+1];
		while(end>=0 && arr[end]>tmp)
		{
			arr[end+1] = arr[end];
			end--;
		}
		arr[end+1] = tmp;//这里在在最后一次移动数据时，堆end减了，所以插入数据的位置时end+1;
	}
}