/**
 * @desc: 直接插入排序
 * 每插入一个数都要将它和之前的已经完成排序的序列进行重新排序，
 * 也就是要找到新插入的数对应原序列中的位置。也就是说，
 * 每次插入一个数都要对原来排序好的那部分序列进行重新的排序，
 * 时间复杂度O（n²）
 * @param $arr
 * @return mixed
 */
function insertSort($arr)
{
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $temp = $arr[$i];
        $j = $i - 1;
        for (; $j >= 0; $j--) {
            if ($temp < $arr[$j]) {
                $arr[$j + 1] = $arr[$j];
            } else {
                break;
            }
        }
        if ($j + 1 != $i) {
            $arr[$j + 1] = $temp;
        }
    }
    return $arr;
}

赞0 2091次