当前位置:首页 > 叨叨念念 > PHP插入排序算法

PHP插入排序算法

叨叨念念 / 星之宇 / 2021-11-20 18:53 / 浏览:170 / 评论:0

PHP插入排序(Insertion Sort)是一种简单直观的排序算法。

工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。


比如:这个数组array(4,3,5,1,2)用冒泡排序算法进行升序排列。

第1个循环循环开始,当前排序:4,3,5,1,2(默认第1个位置已经排序,从第2个位置取数3)

第1趟:取到的数3和第1个位置比较,因为4比3大,所以把数3插入到第1个位置,原第1个位置后移一位。

得到3,4,5,1,2,同时3,4是有序序列。

第2个循环循环开始,当前排序:3,4,5,1,2(从第3个位置取数5)

第1趟:取到的数5和第2个位置数字4,因为4比5小,所以跳出循环。

得到3,4,5,1,2,同时3,4,5是有序序列

第3个循环循环开始,当前排序:3,4,5,1,2(从第4个位置取数1)

第1趟:取到的数1和第3个位置数字5,因为5比1大,所以把数1插入到第3个位置,原第3个位置后移一位。

第2趟:取到的数1和第2个位置数字4,因为4比1大,所以把数1插入到第2个位置,原第2个位置后移一位。

第3趟:取到的数1和第1个位置数字3,因为3比1大,所以把数1插入到第1个位置,原第1个位置后移一位。

得到1,3,4,5,2,同时1,3,4,5是有序序列

第4个循环循环开始,当前排序:1,3,4,5,2(从第5个位置取数2)

第1趟:取到的数2和第4个位置数字5,因为5比2大,所以把数2插入到第4个位置,原第4个位置后移一位。

第2趟:取到的数2和第3个位置数字4,因为4比2大,所以把数2插入到第3个位置,原第3个位置后移一位。

第3趟:取到的数2和第2个位置数字3,因为3比2大,所以把数2插入到第2个位置,原第2个位置后移一位。

第4趟:取到的数2和第1个位置数字1,因为1比2小,所以跳出循环。

至此排序已经完成,得到1,2,3,4,5有序序列。


PHP插入排序代码:

$a=array(4,3,5,1,2);//这里随便创建一个一维数组; 
$n=count($a);//算出数组的元素总个数;
for($i=1; $i<$n; $i++){
    $tmp = $a[$i];
    for ($j = $i-1; $j >= 0; $j--){
        if($a[$j] > $tmp){
            $a[$j+1] = $a[$j];
            $a[$j] = $tmp;
        }else{
            break;
        }
    }
}
print_r($a);

目前有 0 条评论

    • 昵称
    • 邮箱
    • 网址