PHP 数组快排 vs. 归并排序

对于一个文章开发者来说，牢固扎实的基础是十分重要的，golang学习网就来带大家一点点的掌握基础知识点。今天本篇文章带大家了解《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. 归并排序》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！