02-插入排序

/**
 * 插入排序: 每次往后多取一个元素, 和现有元素从后往前逐个比较, 比较大,就将现有元素后移一位
 * 时间复杂度: O(n2)
 * 空间复杂度: O(1)
 * 稳定排序
 */
function insertSort(&$arr) {
    $length = count($arr);
    for($i = 1; $i < $length; ++$i) {// 每次往后多取一个元素
        $temp = $arr[$i];
        for($j = $i - 1; $j >= 0; --$j) {// 和现有元素逐个从后往前比较
            if ($arr[$j] > $temp) { // 比较大,就将现有元素后移一位
                $arr[$j + 1] = $arr[$j];
                $arr[$j] = $temp;
            } else {
                break;
            }
        }
    }
}

$arr = [38, 19, 29, 91, 85, 12, 41, 21];
insertSort($arr);
print_r($arr);


function insertSort2(&$arr) {
    $length = count($arr);
    for($i = 1; $i < $length; ++$i) {// 每次往前多取一个元素
        for($j = 0; $j < $i; ++$j) {// 和现有元素逐个从前往后比较
            if ($arr[$j] > $arr[$i]) { // 找到第一个比它大的元素, 交换, 后续元素往后移一位
                list($arr[$i], $arr[$j]) = [$arr[$j], $arr[$i]];
            }
        }
    }
}

$arr = [38, 19, 29, 91, 85, 12, 41, 21];
insertSort2($arr);
print_r($arr);