此算法主要原理:每次把一个待排序的关键码插入到已排好序的序列中。
排序过程:
1、整个序列分成有序区和无序区,初始化有序区为待排序记录的第一个记录,无序区为剩下的待排序记录。
2、取无序区的第一个记录插入到有序区的合适位置中。
3、重复以上操作直到无序区为空
下面我用具体的数组来演示一遍整体效果
假设有一组待排序数据:8、5、1、9、3
初始 [ 8 ] 5 1 9 3 <strong>中括号代表有序区</strong>
8 向 5 位置后移,5放在 8的前面
第一趟 排序 [ 5 8 ] 1 9 3
5 和 8 各后移一个位置 ,
第二趟排序 [ 1 5 8 ] 9 3
1、5 和 8 不移动,位置不变 ,9放在 8 后面
第三趟排序 [ 1 5 8 9 ] 3
5、8和 9各后移一个位置,1放在3 的前面
第四趟排序 [ 1 3 5 8 9 ]
得到最终结果 1 3 5 8 9
附上我的php代码演示
<?php
$data = array(
1=>8,
2=>5,
3=>1,
4=>9,
5=>3
);
$lenth = count($data);
for($i=2; $i<=$lenth; $i++){
$data[0] = $data[$i];
for($j=$i-1; $data[0]<$data[$j]; $j--){
$data[$j+1] = $data[$j];
}
$data[$j+1] = $data[0];
}
unset($data[0]);
echo "<pre>";print_r($data);die;
?>
以上 使用 $data[0] 是为了防止 数组越界报错使用的,并且充当哨兵的作用。
运行输出如下