PHP 数组快排 vs. 归并排序

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

PHP 数组快排 vs. 归并排序

什么是快排和归并排序？

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

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

代码实现

以下是用 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中文网其他相关文章！