在要排序的一组数中，假设前面的数已经是排好顺序的，

现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。

如此反复循环，直到全部排好顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
$arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39];

function insert_sort($arr)
{
  // 计算数组长度
  $len = count($arr); 
  // 循环数组
  for($i = 1; $i < $len; $i++) {
    // 当前值缓存起来
    $tmp = $arr[$i];
    // 内层循环控制，比较并插入
    for($j = $i - 1; $j >= 0; $j--) {
      
      
      if($tmp < $arr[$j]) {
        //发现插入的元素要小，交换位置，将后边的元素与前面的元素互换
      	$arr[$j + 1] = $arr[$j];
        $arr[$j]		 = $tmp;
      } else {
        //如果碰到不需要移动的元素，由于是已经排序好是数组，则前面的就不需要再次比较了。
        break;
      }
    }
  }
  
  // 返回结果
  return $arr;
}