php插入排序算法

PHP / 107人浏览 / 0人评论

插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

插入排序(Insertion Sort)

插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

插入排序实现:

  • 从第一个元素开始,该元素可以认为已经被排序;第二个和已排序的第一个比较,满足条件插入,默认第一个和第二个已排序;第三个和前面的已排序的数据逐个比较,找到满足条件位置插入,以此类推.....直至排序结束。
<?php
class insertSortObj {
    
    //插入排序
    function insert_sort($arr)
    {
        $len=count($arr);
        for($i=1; $i<$len; $i++) {
            echo "---s--".$i."--s---\n";
            //获得当前需要比较的元素值
            $tmp = $arr[$i];
            //内层循环控制 比较 并 插入
            for($j=$i-1; $j>=0; $j--) {
                //$arr[$i];需要插入的元素
                //$arr[$j];需要比较的元素
                echo '比较:'.$tmp ."<". $arr[$j]."\n";
                if($tmp < $arr[$j])   //从小到大 < || 从大到小 >
                {
                    echo '---:'.$arr[$j+1] ."=". $arr[$j]."\n";
                    //发现插入的元素要小,交换位置
                    //将后边的元素与前面的元素互换
                    $arr[$j+1] = $arr[$j];
    
                    //将前面的数设置为 当前需要交换的数
                    $arr[$j] = $tmp;
                } else {
                    //如果碰到不需要移动的元素
                    //由于是已经排序好是数组,则前面的就不需要再次比较了。
                    break;
                }
            }
            echo "---e--".$i."--e---\n";
        }
        //将这个元素 插入到已经排序好的序列内。
        //返回
        return $arr;
    }
}

$arr = [10, 25, 15, 66, 21, 12, 32, 100, 250, 76, 11,29];

$result = (new insertSortObj())->insert_sort($arr);
var_dump($result);

打印输出

---s--1--s---
比较:25<10
---e--1--e---
---s--2--s---
比较:15<25
---:15=25
比较:15<10
---e--2--e---
---s--3--s---
比较:66<25
---e--3--e---
---s--4--s---
比较:21<66
---:21=66
比较:21<25
---:21=25
比较:21<15
---e--4--e---
---s--5--s---
比较:12<66
---:12=66
比较:12<25
---:12=25
比较:12<21
---:12=21
比较:12<15
---:12=15
比较:12<10
---e--5--e---
---s--6--s---
比较:32<66
---:32=66
比较:32<25
---e--6--e---
---s--7--s---
比较:100<66
---e--7--e---
---s--8--s---
比较:250<100
---e--8--e---
---s--9--s---
比较:76<250
---:76=250
比较:76<100
---:76=100
比较:76<66
---e--9--e---
---s--10--s---
比较:11<250
---:11=250
比较:11<100
---:11=100
比较:11<76
---:11=76
比较:11<66
---:11=66
比较:11<32
---:11=32
比较:11<25
---:11=25
比较:11<21
---:11=21
比较:11<15
---:11=15
比较:11<12
---:11=12
比较:11<10
---e--10--e---
---s--11--s---
比较:29<250
---:29=250
比较:29<100
---:29=100
比较:29<76
---:29=76
比较:29<66
---:29=66
比较:29<32
---:29=32
比较:29<25
---e--11--e---
array(12) {
  [0]=>
  int(10)
  [1]=>
  int(11)
  [2]=>
  int(12)
  [3]=>
  int(15)
  [4]=>
  int(21)
  [5]=>
  int(25)
  [6]=>
  int(29)
  [7]=>
  int(32)
  [8]=>
  int(66)
  [9]=>
  int(76)
  [10]=>
  int(100)
  [11]=>
  int(250)
}

转载注明:

0 条评论

还没有人发表评论

发表评论 取消回复

记住我的信息,方便下次评论
有人回复时邮件通知我