画江湖之算法篇 [排序算法] 插入排序

算法篇

1 插入排序简介

概括:

  • 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
    小伙伴们仔细看下面的动态图哦

完整代码块

public static function insert($arr){
        $size = count($arr);
        for ($i=0; $i <$size-1 ; $i++) {
            for ($j=$i+1; $j >0 ; $j--) {
                if($arr[$j]<$arr[$j-1]){
                    $tmp=$arr[$j];
                    $arr[$j]=$arr[$j-1];
                    $arr[$j-1]=$tmp;
                }
            }
        }
        return $arr;
    }

2 分析代码块 具体分析到代码注释哦 ~

插入排序

public static function insert($arr){
        $size = count($arr);//先计算出数组的大小
        for ($i=0; $i <$size-1 ; $i++) {//外部循环 有多少数组 就循环多少次
            for ($j=$i+1; $j >0 ; $j--) {//内部循环 递减 记住为什么要递减
                if($arr[$j]<$arr[$j-1]){//如果当前的值 小于上一个值 为什么要比较上一个值 为了在已排序序列中从后向前扫描
                    $tmp=$arr[$j];//定义当前值的临时变量
                    $arr[$j]=$arr[$j-1];//替换当前值为上一个值
                    $arr[$j-1]=$tmp;//上一个值替换为当前的值的临时变量
                }
            }
        }
        return $arr;//返回排序好的值
    }
    // print_r(Sort::insert($arr));

3 时间复杂度 分析

file

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L02 从零构建论坛系统》
以构建论坛项目 LaraBBS 为线索,展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 2

你这个不符合数据结构的写法,按道理应该是后移一位而不是交换

4年前 评论

这个方法才是你的动画图的代码
function insert($sort)
{
$count = count($sort);
for($i=1;$i<$count;$i++)
{
$sentinel = $sort[$i];
$j = $i-1;
//前一位比当前哨兵大,则前一位需要往后移动一位
while($j >= 0 && $sort[$j] > $sentinel)
{
$sort[$j+1] = $sort[$j];//$j后移一位
$j--;
}
if($i != $j+1)
{
$sort[$j+1] = $sentinel;
}
}
return $sort;
}

4年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!