php递归实现排序

PHP递归实现排序的方法

递归排序是一种利用函数自我调用来实现排序的算法。以下是几种常见的递归排序实现方法。

快速排序（Quick Sort）

快速排序是一种分治算法，通过选择一个基准元素将数组分成两部分，递归地对子数组进行排序。

function quickSort(array $array): array {
    if (count($array) <= 1) {
        return $array;
    }

    $pivot = $array[0];
    $left = [];
    $right = [];

    for ($i = 1; $i < count($array); $i++) {
        if ($array[$i] < $pivot) {
            $left[] = $array[$i];
        } else {
            $right[] = $array[$i];
        }
    }

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

归并排序（Merge Sort）

归并排序同样采用分治法，将数组分成两半，递归排序后再合并。

function mergeSort(array $array): array {
    if (count($array) <= 1) {
        return $array;
    }

    $mid = (int)(count($array) / 2);
    $left = array_slice($array, 0, $mid);
    $right = array_slice($array, $mid);

    return merge(mergeSort($left), mergeSort($right));
}

function merge(array $left, array $right): array {
    $result = [];

    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] < $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }

    return array_merge($result, $left, $right);
}

注意事项

递归排序算法的时间复杂度通常为 O(n log n)，但在最坏情况下可能退化到 O(n²)。递归深度过大可能导致栈溢出，需注意数据规模。

对于大规模数据，建议使用非递归实现或内置排序函数如 sort()，效率更高且稳定。