排序算法--插入排序

        插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

        算法描述:

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

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

        动图演示:

        代码实现：

function insertSort($arr) {
    $len=count($arr);

    //1. 确定要插入多少回(假设一个数组一次性插入到对的位置，同时第一个位置是假设对的)
    for($i=1; $i < $len; $i++) {
        //2. 取出当前要插入的元素的值
        $tmp = $arr[$i];

        //3. 内层循环控制，比较并插入----让该数据与前面已经排好序的数组元素重复比较(挨个比较)，
        for($j=$i-1; $j>=0; $j--) {
            //4. 比较
            if($tmp < $arr[$j]) {
                //发现插入的元素要小，交换位置，将后边的元素与前面的元素互换
                $arr[$j+1]   = $arr[$j];
                $arr[$j]     = $tmp;
            } else {
                // 如果碰到不需要移动的元素，由于是已经排序好是数组，则前面的就不需要再次比较了。
                // 说明当前带插入元素，比前面的元素要大：说明位置正确
                break;
            }
        }
    }
    return $arr;
}

维基百科：https://en.wikipedia.org/wiki/Insertion_sort 

本文为崔凯原创文章,转载无需和我联系,但请注明来自冷暖自知一抹茶ckhttp://www.cksite.cn

• 上一篇： 排序算法
• 下一篇： 排序算法--选择排序