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

其实就是相当于把数组中的某个数抽出来,然后不断往前比较,小的在前,大的在后。

  • 时间复杂度 o(n^2)
  • 空间复杂度 o(1)
<?php
$a = [3,2,1,5,6,7,322,23,45,9,12,31]; // 要比较的数组
for ($i = 1; $i < count($a); $i++) { // 被抽出来的数
        $cur = $a[$i];
        for ($j = $i - 1; $j >= 0; $j--) { // 比较次数
                if ($a[$j] > $cur) { // 值置换
                        $tmp = $a[$j+1];
                        $a[$j+1] = $a[$j];
                        $a[$j] = $tmp;
                }
        }
}

var_dump($a);