PHP实战中知识总结 / 排序算法 - 直接插入排序算法

直接插入排序的基本思想是 ：将一个记录插入到已排好序的序列中，从而得到一个新的有序序列（将序列的第一个数据看成是一个有序的子序列，然后从第二个记录逐个向该有序的子序列进行有序的插入，直至整个序列有序）。

即每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

$arr = [9,1,5,8,3,7,4,2,20];
$result = $this->sort($arr);
public function insertSort($arr)
{
  $res = [];//要插入的数组
  $res[0] = $arr[0]; //将要排序的第一个值存进数组
  for ($i = 1; $i < count($arr); $i++) {    //循环 1,5,8,3,7,4,6,20
    for ($j = count($res); $j > 0; $j--) {  //循环20,6,4,7,3,8,5,1
      if ($res[$j - 1] > $arr[$i]) {    // 倒序排序（升序则改成<）
        $res[$j] = $arr[$i];
        break;
      } else {
        $tmp = $res[$j - 1];
        $res[$j - 1] = $arr[$i];
        $res[$j] = $tmp;//向后移位
      }
    }
  }
  return $res;
}