php 实现排序算法

以下是用 PHP 实现常见排序算法的示例代码，每种算法均附有简要说明：

冒泡排序

通过多次比较相邻元素并交换位置，将较大元素逐渐移动到数组末端。

function bubbleSort($arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

选择排序

每次遍历选择最小元素，与当前未排序部分的第一个元素交换位置。

function selectionSort($arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }
        $temp = $arr[$i];
        $arr[$i] = $arr[$minIndex];
        $arr[$minIndex] = $temp;
    }
    return $arr;
}

插入排序

将未排序元素逐个插入到已排序部分的正确位置。

function insertionSort($arr) {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
    return $arr;
}

快速排序

采用分治策略，通过基准值将数组分为两部分递归排序。

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

归并排序

将数组递归拆分为最小单元后合并，合并时进行排序。

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

function merge($left, $right) {
    $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);
}

使用示例

$unsorted = [64, 34, 25, 12, 22, 11, 90];
print_r(bubbleSort($unsorted));
print_r(selectionSort($unsorted));
print_r(insertionSort($unsorted));
print_r(quickSort($unsorted));
print_r(mergeSort($unsorted));

以上实现均为基础版本，实际应用中可根据需求优化（如添加提前终止条件、使用迭代代替递归等）。不同算法的时间复杂度从 O(n log n) 到 O(n²) 不等，需根据数据特点选择合适算法。