零、数据结构和算法系列目录

数据结构和算法系列目录(不断更新)：

http://blog.csdn.net/adrastos/article/details/9093857

一、插入排序简介

插入排序是比较简单也比较直接的一种排序算法。对于少量元素待排序数据较为有效。插入排序就像安身高排队，有一个人指挥排队从第二个人开始，按身高把当前的人安插到之前排序好的队列的合适位置。插入排序的每一步是把当前元素插入到已经排好序的相应合适的位置。而整个排序就是从第二个元素开始，依次把当前的元素插入到之前排好序的相应位置。过程实现和简单，但是却与之前讲过的计数排序的原理不一样。插入排序的核心是基于两个数的比较，它是一种比较算法（后面会陆续介绍另外的比较排序）。

二、插入排序的步骤

1. 从待排序数组的第二个元素开始，把当前第i个元素记录在key中
2. 从元素的一个元素开始到当前的第i个元素为止，找到第一个比key大的第j个元素
3. 从第i-1元素开始，用前一个元素覆盖当前元素，直到第j个元素为止。
4. 把key放入到第j个元素中，继续前面的步骤知道结束。

三、插入排序的一些分析

先说明一下，上面的排序是基于数组数据结构排序进行的，基于链表的过程类似。我们来分析一下插入排序的时间复杂度。可以从上面的步骤中看出，算法的核心主要基于两层循环，不难分析出来其时间复杂度为。前面已经介绍过，插入排序是一种基于比较思想的排序算法，而且按照上述步骤的第二步，即找到第一个比key大的元素，这个就保证了算法的稳定性，但是要是把这个条件改变一下。即改成找到第一个大于等于key的元素，这时算法就不是稳定性的算法了，所以对于边界条件的把握一定要注意。

四、插入排序的例子

实现插入排序算法的原理的例子有很多，这里就不在给出，可自行查找具体的例子实现，如算法导论(参考文献1)中的例子。 

五、代码实现

#include <stdio.h>
#include <stdlib.h>

int 
main(int argc, char const *argv[])
{
	int length = 0;
	int i = 0;

	int insert_sort(int *, int);

	while(EOF != scanf("%d", &length))
	{
		int* numbers = (int*)malloc(length * sizeof(int));

		for(i = 0; i < length; i++)
			scanf("%d", &numbers[i]);
		
		insert_sort(numbers, length);

		printf("%d", numbers[0]);
		for(i = 1; i < length; i++)
			printf(" <= %d", numbers[i]);
		printf("\n");

		free(numbers);
	}

	return 0;
}

int 
insert_sort(int *numbers, int length)
{
	int i = 0;
	int j = 0;
	int key = 0;

	for(i = 1; i < length; i++)
	{
		key = numbers[i];
		for(j = i - 1; j >= 0; j--)
		{
			if(key < numbers[j])
				numbers[j + 1] = numbers[j];
			else
				break;
		}
		numbers[j + 1] = key;
	}

	return 0;
}

程序比较简单，就不进行详细的讲解了。

六、后续工作

插入排序只是众多排序算法中的一种。其他排序算法会在后面的一些博客中进行总结。

七、参考资料

1. Introduction to Algorithms(Second Edition), Thomas H.Cormen & Charles E.Leiserson

2. Insert Sort, en.wikipedia.org/wiki/Insertion_sort

说明：

数据结构和算法博客系列的目录为：http://blog.csdn.net/adrastos/article/details/9093857

如有错误还请各位指正，欢迎大家一起讨论给出指导。

上述程序完整代码下载链接：

https://github.com/zeliliu/BlogPrograms/tree/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%26%E7%AE%97%E6%B3%95/sort/insert%20sort​

最后更新时间2013-07-05