排序算法之插入排序

待我称王封你为后i 2022-09-25 15:23 220阅读 0赞

同样的先上这张图

![Center][]

下面分析插入排序：

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

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

插入排序外层循环选择待排元素，时间复杂度为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)，稳定。

[Center]: /images/20220717/d248663106ac43f0a4a175e39b7a2db2.png