03-选择排序

/**
 * 选择排序: 选一个假定的最小, 找到比他小的, 交换位置
 * 时间复杂度: O(n2)
 * 空间复杂度: O(2)
 * 稳定排序
 */
function selectSort(&$arr) {
    $length = count($arr);
    for($i = 0; $i < $length; ++$i) {
        $minIdx = $i;
        for($j = $i + 1; $j < $length; ++$j) {
            if ($arr[$j] < $arr[$minIdx]) {
                $minIdx = $j;
            }
        }
        if ($minIdx != $i) {
            list($arr[$minIdx], $arr[$i]) = [$arr[$i], $arr[$minIdx]];
        }
    }
}

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