时间复杂度为 O (n^2) 的排序算法

今天练习时间复杂度为 O(n^2) 的排序算法

定义数组

$arr = [4,5,6,3,2,1];

$length = count($arr);

冒泡排序

for ($i = 0; $i < $length; $i++) {  //循环次数

    $change = false;  //数据是否有交换

    for ($j = 0; $j < $length - $i - 1 ; $j++) {
        if ($arr[$j] > $arr[$j + 1]) {
            $tmp = $arr[$j];
            $arr[$j] = $arr[$j + 1];
            $arr[$j + 1] = $tmp;
            $change = true;
        }
    }

    if (!$change) {
        break;
    }
}

插入排序

for ($i = 1; $i < $length; $i++) {
    $value = $arr[$i];
    for ($j = $i - 1; $j >= 0; $j--) {
        if ($arr[$j] > $value) {
            $arr[$j + 1] = $arr[$j];
        } else {
            break;
        }
    }
    $arr[$j + 1] = $value;
}

选择排序

for ($i = 0; $i < $length; $i++) {
    $minIndex = $i; //最小值的下标默认为 `i`

    for ($j = $length - 1; $j > $i; $j--) {
        if ($arr[$j] < $arr[$minIndex]) {
            $minIndex = $j;   //最小值下标
        }
    }

    $tmp = $arr[$i];
    $arr[$i] = $arr[$minIndex];
    $arr[$minIndex] = $tmp;

}

本作品采用《CC 协议》，转载必须注明作者和本文链接