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

优化后的冒泡排序 如果在一轮遍历中没有发生任何交换，说明数组已经有序，可以提前终止排序。

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 = [11, 12, 22, 25, 34, 64, 90]; // 已排序数组
$sortedArray = optimizedBubbleSort($unsortedArray);
print_r($sortedArray);

时间复杂度分析

• 最坏情况时间复杂度：O(n²)
• 最好情况时间复杂度：O(n)（当数组已经有序时）
• 平均时间复杂度：O(n²)

冒泡排序适合小规模数据的排序，对于大规模数据效率较低。