插入排序（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;
}
