PHP 冒泡排序

1. 什么是冒泡排序

冒泡排序（Bubble Sort）是一种比较基础的排序算法。

它的核心思想是：

重复比较数组中相邻的两个元素，如果前面的元素比后面的元素大，就交换它们的位置。

每完成一轮比较，当前最大的元素就会移动到数组末尾，就像气泡逐渐“冒”到顶部一样，因此叫做冒泡排序。

例如：

原数组：

[5, 3, 8, 4, 2]

第一轮排序后：

[3, 5, 4, 2, 8]
               ↑
             最大值

2. PHP 实现

<?php

$arr = [5, 3, 8, 4, 2];

$count = count($arr);

// 外层循环控制排序轮数
for ($i = 0; $i < $count - 1; $i++) {

    // 内层循环负责比较相邻元素
    for ($j = 0; $j < $count - 1 - $i; $j++) {

        // 如果前面的数字大于后面的数字，则交换位置
        if ($arr[$j] > $arr[$j + 1]) {

            $temp = $arr[$j];
            $arr[$j] = $arr[$j + 1];
            $arr[$j + 1] = $temp;
        }
    }
}

print_r($arr);

输出：

Array
(
    [0] => 2
    [1] => 3
    [2] => 4
    [3] => 5
    [4] => 8
)

3. 排序过程

假设数组为：

[5, 3, 8, 4, 2]

第一轮

依次比较：

5 和 3 比较

[5, 3, 8, 4, 2]
 ↓  ↓

5 > 3，交换

[3, 5, 8, 4, 2]

继续：

5 和 8 比较

5 < 8，不交换

[3, 5, 8, 4, 2]

继续：

8 和 4 比较

8 > 4，交换

[3, 5, 4, 8, 2]

继续：

8 和 2 比较

8 > 2，交换

[3, 5, 4, 2, 8]

第一轮结束：

[3, 5, 4, 2, 8]
               ↑
          8 已经排好

因此下一轮不需要再比较最后一个元素。

4. 为什么是 $count - 1 - $i

代码中：

for ($j = 0; $j < $count - 1 - $i; $j++)

这里的 $i 很重要。

因为每完成一轮排序，就会有一个最大的元素被移动到数组最后面。

例如：

第一轮：

[3, 5, 4, 2, 8]
               ↑
              不用比

第二轮：

[3, 4, 2, 5, 8]
            ↑  ↑
            都不用比

所以随着 $i 增加，需要比较的元素会越来越少。

5. 优化版冒泡排序

如果某一轮排序过程中一次交换都没有发生，说明数组已经是有序的，可以直接结束排序。

<?php

function bubbleSort(array $arr): array
{
    $count = count($arr);

    for ($i = 0; $i < $count - 1; $i++) {

        $swapped = false;

        for ($j = 0; $j < $count - 1 - $i; $j++) {

            if ($arr[$j] > $arr[$j + 1]) {

                [$arr[$j], $arr[$j + 1]] = [
                    $arr[$j + 1],
                    $arr[$j]
                ];

                $swapped = true;
            }
        }

        // 一次交换都没有发生，说明已经有序
        if (!$swapped) {
            break;
        }
    }

    return $arr;
}

$arr = [5, 3, 8, 4, 2];

print_r(bubbleSort($arr));

PHP 可以使用：

[$arr[$j], $arr[$j + 1]] = [
    $arr[$j + 1],
    $arr[$j]
];

直接交换两个元素，不需要额外定义 $temp。

6. 时间复杂度

普通冒泡排序的时间复杂度为：

O(n²)

例如有 n 个元素，大致需要进行：

(n - 1) + (n - 2) + ... + 1

次比较。

因此，当数据量比较大的时候，冒泡排序效率并不高。

使用 $swapped 优化之后，如果数组本身已经有序：

[1, 2, 3, 4, 5]

第一轮发现没有任何元素发生交换，就可以直接结束。

这种情况下最好时间复杂度可以达到：

O(n)

7. 总结

冒泡排序可以简单理解成：

比较相邻元素
    ↓
顺序不对就交换
    ↓
继续比较下一对
    ↓
一轮结束
    ↓
最大值移动到最后
    ↓
重复以上过程

核心代码：

for ($i = 0; $i < $count - 1; $i++) {

    for ($j = 0; $j < $count - 1 - $i; $j++) {

        if ($arr[$j] > $arr[$j + 1]) {

            [$arr[$j], $arr[$j + 1]] = [
                $arr[$j + 1],
                $arr[$j]
            ];
        }
    }
}

记忆重点：

冒泡排序就是不断比较相邻的两个元素，大的往后移动；每完成一轮，就确定一个最大的元素。