排序算法之插入排序-蒲公英云

排序算法之插入排序

同样的先上这张图

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;
    }
}