工作中业务逻辑写多了，对算法越来越陌生，决定从最基础的排序重拾算法。
在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位，这种算法叫做插入排序。（算法（第四版））
算法（第四版）代码：
/* 插入排序 */ function insertSort(&$a) { $num = count($a); $z = 0; $loopNum = 0; $exchNum = 0; for ($i = 1; $i < $num; $i++) { $min = $i; for ($j = $i; $j > 0; $j--) { $loopNum++; if (less($a[$j], $a[$j-1])) { exch($a, $j, $j-1); $exchNum++; } } } var_dump('insert loop num -----' . $loopNum); var_dump('insert exch num-----' . $exchNum); }
结果：
测试数据：[0,1,2,7,123,12,9,5];
看完代码，发现其实数组左边总是保持有序，是不是当待插入元素值大于左边有序数组的某元素，内循环就可以中断，减少循环次数？
因此有了下面代码。
自我改进代码：
/* 插入排序 */ function insertSort(&$a) { $num = count($a); $z = 0; $loopNum = 0; $exchNum = 0; for ($i = 1; $i < $num; $i++) { $min = $i; for ($j = $i; $j > 0; $j--) { $loopNum++; if (less($a[$j], $a[$j-1])) { exch($a, $j, $j-1); $exchNum++; } else { //前面既然已经排好序，那碰到 break; } } } var_dump('insert loop num -----' . $loopNum); var_dump('insert exch num-----' . $exchNum); }
结果：
测试数据：[0,1,2,7,123,12,9,5];
从两次结果可以看出，交换次数是没有变化的，循环次数少了一半。
这个应该很多人都知道了，只是我才发现。
看完代码，发现其实数组左边总是保持有序，是不是
