插入排序------基本有序序列的最佳选择

插入排序（Insertion Sort）是又一经典排序算法，因每次将一个新元素插入到有序序列并保持序列有序而得名。插入排序是处理基本有序序列的最佳选择。

算法原理/步骤

从序列中取出第一个元素，形成一个有序序列；
从待排序序列中取出下一个元素，从有序序列尾部向前开始检索，找到一个位置，使得将新元素放在该处后，仍然有序；
将该元素插入到该位置
重复过程2、3，直到取完所有元素；

(来自维基百科)

时间复杂度

从算法原理中可以看到，每次只对一个元素进行排序，故原序列第K个位置上的元素最多需要K次比较和1次赋值、最少1次比较和1次赋值即可完成，故时间复杂度最快为O(N)，最差为O(N^2)，平均为O(N^2)。注：最好情况：序列有序；最坏：序列逆序。

稳定性

插入排序中元素间交换不是跳跃性的，所以是稳定的排序。

算法演示

下面给出是对某组数据进行排序的过程演示。（还是维基的）

注：演示的过程与文中所给代码有些许差异，在于图片中先找到位置再插入，而文中代码则是一边检索位置一边交换。对应的代码请点击查看查看。

更加高大上的演示，请猛击这里

实例代码

#include<iostream>
#include<cstdlib>
#include<ctime>

using namespace std;

#define MAXN 10

int insert_sort(int *, int);

int main()
{
	int src[MAXN];
	for(int i=0; i<MAXN; i++)
		src[i] = rand()%10000;//先随机生成MAXN个数字，做测试用

	for(int i=0; i<MAXN; i++)
		cout<<src[i]<<" ";
	cout<<endl;//输出原始数据

	//执行插入排序
	insert_sort(src, MAXN);

	/*检查排序结果*/
	for(int i=0; i<MAXN-1; i++)
	{
		if(src[i]>src[i+1]){
			cout<<"wrong"<<endl;
		}
	}

	cout<<"sort finished!"<<endl;
	return 0;
}


int insert_sort(int *src, int size)
{
	for(int i=0; i<size; i++)
	{
		//从第一个元素开始，每次取出一个加入到有序序列中
		int j=i;
		while(j<0 && c[j-1])
		{
			//找到新元素在有序序列中的位置
			swap(src[j], src[j-1]);
			j--;
		}
	}

	return 0;
}

算法改进

文中给出的代码在处理每一个元素时，都会经过最多i次比较、K次交换（3次赋值）。可以通过先比较得出位置再赋值的办法来减少赋值（K+1次交换）。
检索位置过程中利用二分查找可以减少一定次数的比较。
添加哨兵节点（即在序列头加入一个无穷小的元素），减少越界判断操作。（想出这办法的人太聪明了）

总结

插入排序算法是一种思想简单明了的算法，在处理一些基本有序的序列上甚至优于其他算法，例如快速排序。

详细代码请点击这里查看。