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

$optimizedSortedArray = optimizedBubbleSort($unsortedArray);
print_r($optimizedSortedArray);

性能分析

冒泡排序的时间复杂度为O(n²)，在最坏情况下需要进行n(n-1)/2次比较和交换。优化后的版本在某些情况下可以减少不必要的遍历，但平均时间复杂度仍为O(n²)。适合小规模数据排序，对于大规模数据建议使用更高效的算法如快速排序或归并排序。