php实现冒泡排序

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;
}

优化版本（减少不必要的遍历）

如果某一轮遍历中没有发生交换，说明数组已有序，可以提前终止排序：

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;
}

使用示例

$unsortedArray = [64, 34, 25, 12, 22, 11, 90];
$sortedArray = bubbleSort($unsortedArray);
print_r($sortedArray);

输出结果：

Array
(
    [0] => 11
    [1] => 12
    [2] => 22
    [3] => 25
    [4] => 34
    [5] => 64
    [6] => 90
)

时间复杂度分析

• 最坏情况（完全逆序）：O(n²)
• 最好情况（已排序）：优化后为O(n)
• 平均情况：O(n²)