插入排序算法的实现逻辑是:不断的将待排序元素的第一个元素,插入到前面的已排序元素中顺序位置,从而已排序元素长度加1并继续有序;而在插入过程中,已排序元素中比待插入元素大的元素,位置需要向后移动,以便给待插入元素提供位置。
以下是实现插入排序的php代码
<?php
$array = [9,1,3,5,2,8,7,6,4];
function insert_sort($array)
{
for ($i = 1;$i < count($array);$i++){
$tmp = $array[$i];
for ($j = $i - 1;$j >= 0 && $array[$j] > $tmp;$j--){
$array[$j + 1] = $array[$j];
}
$array[$j+1] = $tmp;
}
return $array;
}
$array = insert_sort($array);
print_r($array);
排序结果
Array
(
[0] => 1
[1] => 2
[2] => 3
[3] => 4
[4] => 5
[5] => 6
[6] => 7
[7] => 8
[8] => 9
)
为更好理解插入排序,下面把插入和移动过程打印出来,php代码
<?php
$array = [9,1,3,5,2,8,7,6,4];
function insert_sort($array)
{
for ($i = 1;$i < count($array);$i++){
echo "####\n";
$tmp = $array[$i];
echo "开始对".$tmp."排序\n";
for ($j = $i - 1;$j >= 0 && $array[$j] > $tmp;$j--){
$array[$j + 1] = $array[$j];
echo $array[$j]."后移:".implode(",",$array)."\n";
}
$array[$j+1] = $tmp;
echo $tmp."向前插入\n";
echo "结果:".implode(",",$array)."\r\n\r\n";
}
return $array;
}
$array = insert_sort($array);
打印插入和移动过程
####
开始对1排序
9后移:9,9,3,5,2,8,7,6,4
1向前插入
结果:1,9,3,5,2,8,7,6,4
####
开始对3排序
9后移:1,9,9,5,2,8,7,6,4
3向前插入
结果:1,3,9,5,2,8,7,6,4
####
开始对5排序
9后移:1,3,9,9,2,8,7,6,4
5向前插入
结果:1,3,5,9,2,8,7,6,4
####
开始对2排序
9后移:1,3,5,9,9,8,7,6,4
5后移:1,3,5,5,9,8,7,6,4
3后移:1,3,3,5,9,8,7,6,4
2向前插入
结果:1,2,3,5,9,8,7,6,4
####
开始对8排序
9后移:1,2,3,5,9,9,7,6,4
8向前插入
结果:1,2,3,5,8,9,7,6,4
####
开始对7排序
9后移:1,2,3,5,8,9,9,6,4
8后移:1,2,3,5,8,8,9,6,4
7向前插入
结果:1,2,3,5,7,8,9,6,4
####
开始对6排序
9后移:1,2,3,5,7,8,9,9,4
8后移:1,2,3,5,7,8,8,9,4
7后移:1,2,3,5,7,7,8,9,4
6向前插入
结果:1,2,3,5,6,7,8,9,4
####
开始对4排序
9后移:1,2,3,5,6,7,8,9,9
8后移:1,2,3,5,6,7,8,8,9
7后移:1,2,3,5,6,7,7,8,9
6后移:1,2,3,5,6,6,7,8,9
5后移:1,2,3,5,5,6,7,8,9
4向前插入
结果:1,2,3,4,5,6,7,8,9
以上便是插入排序的插入和移动的具体过程。