php基础教程-数组插入排序算法[技术分享]

插入排序

1、认定一个第一个元素已经排好序

2、取出第二个元素作为待插入元素

3、将待插入元素与已排好元素比较

4、若小于已排好元素,则说明前面排序未在正确位置,应该向后移动,让新元素插入进去

5、重复以上操作,直到该元素插入完毕

6、重复操作,直至所有元素完毕

示例地址:https://www.vqqc.cn/try/php/basics/insert.php

<?php

//PHP数组排序:插入排序

$arr = arrray(4,2,6,8,9,5);

// 1、 确定要插入多少回(假设一个数组一次性插入到对的位置,同时第一个位置是假设对的)

for($i = 1, $len = count($arr); $i < $len;$i++){
    //2、 取出当前要插入的元素的值
    $temp = $arr[$i];
    // 3、 让该数据与前面已经排好序的数组元素重复比较(挨个比较),直到的位置(交换)
    for($j = $i - 1; $j >= 0; $j--) {
        // 4、 比较
        if($arr[$j] > $temp){
            // 说明当前要插入的元素,比前面的已经排好序的值要小:交换位置
            $arr[$j+1] = $arr[$j];
            $arr[$j] = $temp;
        }else {
            //说明当前待插入元素,比前面的元素要大:说明位置正确.
            break;
        } 
    }
}

echo '<pre>';
print_r($arr);

优化代码

优化代码地址:https://www.vqqc.cn/try/php/basics/insert_op.php

<?php

//PHP数组排序:插入排序

$arr = array(4,2,6,8,9,5);

// 1、 确定要插入多少回(假设一个数组一次性插入到对的位置,同时第一个位置是假设对的)

for($i = 1, $len = count($arr); $i < $len;$i++){
    //2、 取出当前要插入的元素的值
    $temp = $arr[$i];

    // 标记:默认说明当前要插入的数组的 位置是对的
    $change = false;
    
    // 3、 让该数据与前面已经排好序的数组元素重复比较(挨个比较),直到的位置(交换)
    for($j = $i - 1; $j >= 0; $j--) {
        // 4、 比较
        if($arr[$j] > $temp){
            // 说明当前要插入的元素,比前面的已经排好序的值要小:交换位置
            $arr[$j+1] = $arr[$j];
            
            // 说明前面顺序的数组元素有不合适的位置
            $change = true;
        }else {
            //说明当前待插入元素,比前面的元素要大:说明位置正确.
            break;
        } 
    }
    
    // 判断位置需要变动
    if($change){
        // 有数据移动:占错位置
        $arr[$j+1] = $temp;
        
    }
}

echo '<pre>';
print_r($arr);

优化代码二

优化代码地址:https://www.vqqc.cn/try/php/basics/insert_optwo.php

<?php
$arr = [4,2,6,8,9,5];

$len = count($arr);

for($i = 1;$i<$len;$i++)   // 第几个元素为待插入元素
{
    $tmp = $arr[$i];
    for($j = $i;$j>0;$j--)  // 比较几次
    {
        if($tmp < $arr[$j-1])    // 注意此处比较的是tmp
            $arr[$j] = $arr[$j-1];
        else
            break;
    }
    if($arr[$j] != $tmp)
        $arr[$j] =$tmp;
}

var_dump($arr);

// 交换值
function swap1(&$a,&$b)
{
    $tmp = $a;
    $a = $b;
    $b = $tmp;
}

返回结果

Array
(
    [0] => 2
    [1] => 4
    [2] => 5
    [3] => 6
    [4] => 8
    [5] => 9
)
© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容