插入排序

插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

基本思想

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法。

将n个元素的数列分为已有序和无序两个部分，如下所示：

{{a1}，{a2，a3，a4，…，an}}

{{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}}

…

{{a1(n-1），a2(n-1) ，…},{an(n-1)}}

每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。

算法步骤

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

⒈ 从第一个元素开始，该元素可以认为已经被排序

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

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

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

⒌ 将新元素插入到下一位置中

⒍ 重复步骤2，直到将最后一个元素插入到已排序序列中

C语言示例代码

　　示例代码为C语言，输入参数中，需要排序的数组为array[]，起始索引为first，终止索引为last。示例代码的函数采用in-place排序，调用完成后，array[]中从first到last处于升序排列。

#include <stdio.h>

void print_array(int *array, int length)
{
	int i = 0;
	while(i < length)
		printf("%d  ", array[i++]);
	printf("n");
}

void insertion_sort(int *array,unsigned int first,unsigned int last)
{
	//默认array第first位置的那个元素有序（本身只有一个元素）
	unsigned int i, j;
	int temp;
	//变量i始终指向无序数列的第一个元素
	for( i = first + 1; i < last; i++)
	{
		temp = array[i];
		for(j = i; (j > first) && (array[j - 1]) > temp; j--)
		{
			array[j] = array[j - 1];
		}
		array[j] = temp;
	}
}

int main(void)
{
	int array[10] = {4,1,7,8,5,3,9,5,6,3};
	print_array(array,10);
	insertion_sort(array, 0, 9);
	print_array(array,10);
	getchar();
	return 0;
}

运行结果如下：