PHP实现插入排序算法

插入排序算法的实现逻辑是：不断的将待排序元素的第一个元素，插入到前面的已排序元素中顺序位置，从而已排序元素长度加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

以上便是插入排序的插入和移动的具体过程。

推荐文章