PHP 排序算法

2018-10-15

冒泡排序

冒泡排序比较简单，每一次循环从前往后依次比较，如果前者比后者大，则交换位置，就像泡泡越来越大一样，重复上面的循环，直到数组有序，最多循环次数为 n^2，可以通过添加一个交换变量来进行优化，如果一次循环中没有发生交换的话，则表明排序完成。

function bubbleSorting($arr)
{
    $len = count($arr);
    // 最外层循环
    for ($i = 0; $i < $len; $i++) {
        // 交换旗帜变量
        $swapFlag = false;
        // 这一层循环每次会选出最大的值放在最后
        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$i] > $arr[$j]) {
                $swapFlag = true;
                // 交换
                $temp = $arr[$i];
                $arr[$i] = $arr[$j];
                $arr[$j] = $temp;
            }
        }
        // 没有发生交换，排序完成，退出循环
        if ($swapFlag === false) {
            break;
        }
    }

    return $arr;
}

选择排序

每一次循环都选出最小的数放在前面的位置，重复上面的循环，直到数组有序。

function selectSorting($arr)
{
    $len = count($arr);
    // 最外层循环
    for ($i = 0; $i < $len; $i++) {
        // 假定第一个数最小，记录下标
        $min = $i;
        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$min] > $arr[$j]) {
                $min = $j;
            }
        }
        // 如果下标改变，则进行交换
        if ($min != $i) {
            $temp = $arr[$min];
            $arr[$min] = $arr[$i];
            $arr[$i] = $temp;
        }
    }

    return $arr;
}

插入排序

把数组看成一个有序表和无序表，如第一个数由为有序表，n-1 个数为无序表，每一次循环都从无序表取一个数放进有序表中，重复上面的循环，直到数组有序。

function insertSorting($arr)
{
    $len = count($arr);
    // 无序表循环
    for ($i = 1; $i < $len; $i++) {
        // 要放进有序表中的数
        $temp = $arr[$i];
        // 有序循环
        for ($j = $i - 1; $j >= 0; $j--) {
            // 将取出的数放进有序表中正确的位置
            if ($temp < $arr[$j]) {
                $arr[$j + 1] = $arr[$j];
                $arr[$j] = $temp;
            }
        }
    }

    return $arr;
}

快速排序

选定一个基准数，如第一个，每一次循环都将剩余的元素分成两部分，一部分比基准数小，一部分比基准数大，将这两部分数进行递归排序，最后合并得到有序数组。

function quickSorting($arr)
{
    $len = count($arr);
    // 如果只剩一个数，直接返回
    if ($len <= 1) {
        return $arr;
    }

    // 选取基数
    $base = $arr[0];
    $left = [];
    $right = [];

    for ($i = 1; $i < $len; $i++) {
        if ($arr[$i] < $base) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }

    // 递归
    $left = quickSorting($left);
    $right = quickSorting($right);

    return array_merge($left, [$base], $right);
}

参考

VisuAlgo - 排序