php冒泡排序实现

冒泡排序原理

冒泡排序是一种简单的排序算法，通过重复遍历待排序的列表，比较相邻元素并交换位置，将较大（或较小）的元素逐渐“冒泡”到列表的一端。每一轮遍历会将当前未排序部分的最大（或最小）元素移动到正确位置。

PHP实现代码

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

// 示例用法
$unsortedArray = [64, 34, 25, 12, 22, 11, 90];
$sortedArray = bubbleSort($unsortedArray);
print_r($sortedArray);

代码说明

• 外层循环：控制排序轮数，共需 $length - 1 轮。
• 内层循环：比较相邻元素，若前一个元素大于后一个，则交换位置。每轮结束后，最大的元素会被移动到末尾。
• 时间复杂度：最坏情况下为 O(n²)（完全逆序），最好情况下为 O(n)（已有序时可通过优化提前终止）。

优化版本

添加标志位判断是否已有序，减少不必要的遍历：

function optimizedBubbleSort($array) {
    $length = count($array);
    for ($i = 0; $i < $length - 1; $i++) {
        $swapped = false;
        for ($j = 0; $j < $length - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
                $swapped = true;
            }
        }
        if (!$swapped) break; // 本轮无交换，提前结束
    }
    return $array;
}