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

1. 算法描述

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

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

2. 动图演示

image

3. 代码实现

<?php
//输出数组序列
function echo_arr($arr, $sym=' '){
    echo implode($sym, $arr).'<br>';
}

$arr = array( 6, 4, 7, 2, 9, 8, 1 );
echo_arr($arr);
$arr = insert_sort($arr);
echo_arr($arr);

function insert_sort($arr){
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $preIndex = $i - 1;
        $current = $arr[$i];
        while ($preIndex >= 0 && $arr[$preIndex] > $current) {
            $arr[$preIndex + 1] = $arr[$preIndex];
            $preIndex--;
        }
        $arr[$preIndex + 1] = $current;
    }
    return $arr;
}