排序算法之插入排序

同样的先上这张图

下面分析插入排序：

插入排序每次取一个元素插入到已排好序的序列中。

由于前面的序列已经排好序，我们只需要从这个序列的后面开始查找，找到第一个大于待插入元素的位置，将该位置后面的元素全部往后移一个位置，并把待排元素插入到该位置之后。

插入排序外层循环选择待排元素，时间复杂度为O(n)，内层循环找插入位置，最好情况是直接插入到最后，时间复杂度为O(1），最坏情况可能是插入到开头，时间复杂度为O(n)，所以插入排序最好情况时间复杂度为O(n)，平均情况和最坏情况时间复杂度为O(n2)。

插入排序不需要额外的辅助空间，空间复杂度为O(1)。

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面，所以插入排序是稳定的。

AS3代码：

		/**
		 * 插入排序
		 * 外层循环选择待插入元素
		 * 内层循环查找插入位置并将该位置后面元素后移
		 */
		private function InsertSort(arr:Array):void{
			var x:Number,j:Number;
			//外层循环从1到n-1，选择待插入元素
			for(var i:uint=1;i<arr.length;i++){
				//如果arr[i]>=arr[i-1]直接插入到最后
				if(arr[i]<arr[i-1]){
					//复制为哨兵
					x=arr[i];
					j=i-1;
					while(x<arr[j] && j>=0){
						arr[j+1]=arr[j];
						j--;
					}
					arr[j+1]=x;
				}
			}
		}

c++代码

/*
* 插入排序
* 外层循环遍历待插入元素
* 内层循环从已排好序元素中查找插入位置
* 最好情况O(n),最坏和平均情况O(n2)
* O(1)
* 稳定
*/
template <typename T>
void SortHelp<T>::insertSort(T l[], int length) {
	int temp, j;
	for (int i = 1; i < length; i++)
	{
		//查找插入位置的同时将元素往后移
		j = i - 1;
		temp = l[i];
		while (l[j] > temp && j >= 0)
		{
			l[j + 1] = l[j];
			j--;
		}
		//插入
		l[j + 1] = temp;
	}
}

总结，插入排序最好时间复杂度为O(n)，最坏及平均时间复杂度为O(n2)；空间复杂度为O(1)，稳定。