插入排序（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)
}