PHP 经典的四大排序算法

PHP 经典的四大排序算法，每种算法各有优缺点，适合不同的应用场景

1.冒泡排序（Bubble Sort）

描述：反复遍历数组，相邻元素两两比较并交换，将最大的元素逐渐“冒泡”到数组末尾。
复杂度：平均时间复杂度 O(n²)，空间复杂度 O(1)。
优点：实现简单，适合小规模数据。
缺点：效率较低，不适合大规模数据。
应用：适合数据量少、排序要求不高的场景。

function bubbleSort($array) {
    $n = count($array);
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                // 交换相邻元素
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }
    return $array;
}

2.选择排序（Selection Sort）

描述：遍历数组，找到最小的元素放到排序部分的末尾，逐步扩展排序部分。
复杂度：平均时间复杂度 O(n²)，空间复杂度 O(1)。
优点：不依赖数组的顺序，交换次数较少。
缺点：时间复杂度较高，不适合数据量较大的场景。
应用：适合内存受限、数据量不大的排序任务。

function selectionSort($array) {
    $n = count($array);
    for ($i = 0; $i < $n - 1; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($array[$j] < $array[$minIndex]) {
                $minIndex = $j;
            }
        }
        // 交换元素
        $temp = $array[$i];
        $array[$i] = $array[$minIndex];
        $array[$minIndex] = $temp;
    }
    return $array;
}

3.快速排序（Quick Sort）

描述：选择一个“基准”元素，将数组分为小于和大于基准的两部分，然后对这两部分递归排序。
复杂度：平均时间复杂度 O(n log n)，空间复杂度 O(log n)。
优点：速度快、效率高，是常用的排序算法之一。
缺点：最坏情况下时间复杂度为 O(n²)，但可以通过随机选基准元素来避免。
应用：广泛应用于数据量大、性能要求高的场景。

function quickSort($array) {
    if (count($array) < 2) {
        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));
}

4.归并排序（Merge Sort）

描述：将数组分成两半，分别排序后合并成一个有序数组（递归实现）。
复杂度：时间复杂度 O(n log n)，空间复杂度 O(n)。
优点：稳定排序，适合大数据量排序，最坏情况也有较好性能。
缺点：需要额外的空间存储数组，不适合内存非常受限的场景。
应用：适合排序较大数据集，且对稳定性有要求的场景。

function mergeSort($array) {
    if (count($array) <= 1) {
        return $array; // 基线条件
    }

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

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

function merge($left, $right) {
    $result = [];
    $i = $j = 0;

    // 合并两个已排序数组
    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] < $right[$j]) {
            $result[] = $left[$i];
            $i++;
        } else {
            $result[] = $right[$j];
            $j++;
        }
    }

    // 合并剩余元素
    while ($i < count($left)) {
        $result[] = $left[$i];
        $i++;
    }

    while ($j < count($right)) {
        $result[] = $right[$j];
        $j++;
    }

    return $result;
}