1. 概述

  • 思路：轮询数组， 记录轮询到当前位置的最小的元素，将当前元素插入到前面组成的新序中合适的位置。
  • 稳定性：稳定

  • 优化：折半插入（顾名思义，在检测当前数应该插入的位置时，不使用原来的迭代，而是使用二分来查找，二分也就是折半）

    2. 实现代码

    ```php <?php class InsertSort { private $ori = []; public $new = []; public function __construct(array $arr) {

    1.   $this->ori = $arr;
    2.   $r = $this->insert($this->ori);
    3.   $this->new = $r;

    }

    private function insert(array $arr) {

    1.   for ($i = 1; $i < count($arr); $i++) {
    2.       for ($j = $i; $j > 0; $j--) {
    3.           if ($arr[$j] < $arr[$j - 1]) {
    4.               $arr = self::swap($arr, $j, $j - 1);
    5.           }
    6.       }
    7.   }
    8.   return $arr;

    }

    public static function swap(array $arr, int $i, int $j) {

    1.   $tmp = $arr[$i];
    2.   $arr[$i] = $arr[$j];
    3.   $arr[$j] = $tmp;
    4.   return $arr;

    } }

$arr = [5, 3, 6, 8, 1, 7, 9, 4, 2]; $cls = new InsertSort($arr); print_r($cls->new); ```