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

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

代码解析

• 外层循环 $i 控制排序的轮数，共需 $length - 1 轮。
• 内层循环 $j 比较相邻元素，如果前一个元素大于后一个元素，则交换它们的位置。
• 每轮内层循环结束后，最大的元素会被移动到数组的末尾。
• 最终返回排序后的数组。

优化冒泡排序

可以通过添加标志位来优化冒泡排序，减少不必要的比较：

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

• 添加 $swapped 标志位，如果在某一轮内层循环中没有发生交换，说明数组已经有序，可以提前退出循环。

时间复杂度分析

• 最坏情况时间复杂度为 O(n²)，发生在数组完全逆序时。
• 最好情况时间复杂度为 O(n)，发生在数组已经有序时（优化版本）。
• 平均时间复杂度为 O(n²)。