十大排序算法之插入排序

2017-03-25

本文总阅读量0次

(1)算法简介

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

(2)算法描述和实现

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

<1>.从第一个元素开始，该元素可以认为已经被排序；
<2>.取出下一个元素，在已经排序的元素序列中从后向前扫描；
<3>.如果该元素（已排序）大于新元素，将该元素移到下一位置；
<4>.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
<5>.将新元素插入到该位置后；

<6>.重复步骤2~5。

javascript代码实行

function insertionSort(array) {
    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
        console.time('插入排序耗时：');
        for (var i = 1; i < array.length; i++) {
            var key = array[i];
            var j = i - 1;
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
        console.timeEnd('插入排序耗时：');
        return array;
    } else {
        return 'array is not an Array!';
    }
}

改进插入排序：查找插入位置时使用二分查找的方式

function binaryInsertionSort(array) {
    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
        console.time('二分插入排序耗时：');
        for (var i = 1; i < array.length; i++) {
            var key = array[i], left = 0, right = i - 1;
            while (left <= right) {
                var middle = parseInt((left + right) / 2);
                if (key < array[middle]) {
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            }
            for (var j = i - 1; j >= left; j--) {
                array[j + 1] = array[j];
            }
            array[left] = key;
        }
        console.timeEnd('二分插入排序耗时：');
        return array;
    } else {
        return 'array is not an Array!';
    }
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(binaryInsertionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

PHP代码实现：

 function insertSort($arr) {
     //区分 哪部分是已经排序好的
     //哪部分是没有排序的
     //找到其中一个需要排序的元素
     //这个元素 就是从第二个元素开始，到最后一个元素都是这个需要排序的元素
     //利用循环就可以标志出来
     //i循环控制 每次需要插入的元素，一旦需要插入的元素控制好了，
     //间接已经将数组分成了2部分，下标小于当前的（左边的），是排序好的序列
    $len=count($arr);     
    for ($i=1; $i < $len; $i++) {
        //获得当前需要比较的元素值。
        $tmp = $arr[$i];
        //内层循环控制 比较 并 插入
        for ($j = $i - 1; $j >= 0; $j--) {
            //$arr[$i];//需要插入的元素; $arr[$j];//需要比较的元素
            if ($tmp < $arr[$j]) {
                //发现插入的元素要小，交换位置
                //将后边的元素与前面的元素互换
                $arr[$j + 1] = $arr[$j];
                //将前面的数设置为 当前需要交换的数
                $arr[$j] = $tmp;
            } else {
                //如果碰到不需要移动的元素
                //由于是已经排序好是数组，则前面的就不需要再次比较了。
                break;
            }
        }
    }
    //将这个元素 插入到已经排序好的序列内。
    //返回
    return $arr;
}

php插入排序算法改进(二分插入排序算法)：

function BinInsertSort($arr)   
{   
        var $key, $left, $right, $middle;   
        var len=count($arr);
        for (var i=1; i<$len; $i++)   
        {   
                $key = arr[$i];   
                $left = 0;   
                $right = $i-1;   
                while ($left<=$right)   
                {   
                        $middle = ($left+$right)/2;   
                        if (arr[$middle]>$key)   
                                $right = $middle-1;   
                        else   
                                $left = $middle+1;   
                }   
                   
                for(var $j=$i-1; $j>=$left; $j--)   
                {   
                        arr[$j+1] = a[$j];   
                }   
                   
                arr[$left] = $key;          
        }   
   retrun $arr;
}

(3)算法分析

最佳情况：输入数组按升序排列。T(n) = O(n)
最坏情况：输入数组按降序排列。T(n) = O(n2)
平均情况：T(n) = O(n2)