PHP 数组快排 vs. 归并排序-php教程-PHP中文网

PHP 数组快排 vs. 归并排序

WBOY

发布： 2024-04-26 12:45:02

原创

1175人浏览过

快排是一种递归算法，将数组划分成较小元素和较大元素两部分并递归排序，而归并排序将数组递归地分成较小的数组，对每个小数组排序，再合并回原始数组。php 实现的代码分别为：快排：将数组划分为小于和大于基准值的元素，然后对每个部分进行递归排序。归并排序：将数组递归地分成较小的数组，对每个较小的数组排序，然后将排序后的较小的数组合并回原始数组。

PHP 数组快排 vs. 归并排序

PHP 数组快排 vs. 归并排序

什么是快排和归并排序？

快排和归并排序都是用于对数组进行排序的常见算法。

立即学习“PHP免费学习笔记（深入）”；

快排：将数组划分为两个部分，一个包含较小的元素，另一个包含较大的元素，然后递归地对每个部分排序。
归并排序：将数组递归地分成较小的数组，对每个较小的数组排序，然后将排序后的较小的数组合并回原始数组。

代码实现

以下是用 PHP 实现的快排和归并排序函数：

快排：

function quickSort($arr) {
    if (count($arr) <= 1) {
        return $arr;
    }
    $pivot = $arr[0];
    $left = [];
    $right = [];
    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

登录后复制

归并排序：

function mergeSort($arr) {
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }
    $mid = floor($length / 2);
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);
    return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right) {
    $result = [];
    $lIndex = $rIndex = 0;
    while ($lIndex < count($left) && $rIndex < count($right)) {
        if ($left[$lIndex] < $right[$rIndex]) {
            $result[] = $left[$lIndex++];
        } else {
            $result[] = $right[$rIndex++];
        }
    }
    while ($lIndex < count($left)) {
        $result[] = $left[$lIndex++];
    }
    while ($rIndex < count($right)) {
        $result[] = $right[$rIndex++];
    }
    return $result;
}

登录后复制

实战案例

考虑一个无序的整数数组 [5, 2, 8, 3, 1, 9, 4, 7, 6].

使用快排：

$sortedArray = quickSort([5, 2, 8, 3, 1, 9, 4, 7, 6]);
print_r($sortedArray);

登录后复制

输出：

[1, 2, 3, 4, 5, 6, 7, 8, 9]

登录后复制

使用归并排序：

$sortedArray = mergeSort([5, 2, 8, 3, 1, 9, 4, 7, 6]);
print_r($sortedArray);

登录后复制

输出：

[1, 2, 3, 4, 5, 6, 7, 8, 9]

登录后复制

以上就是PHP 数组快排 vs. 归并排序的详细内容，更多请关注php中文网其它相关文章！