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

时间复杂度分析

冒泡排序的时间复杂度为O(n²)，最坏情况下需要进行n(n-1)/2次比较和交换。优化后的版本在最好情况下(已排序数组)时间复杂度为O(n)。

适用场景

冒泡排序适用于小规模数据排序或教学目的，对于大规模数据排序效率较低，通常选择更高效的排序算法如快速排序或归并排序。