冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行,直到没有再需要交换的元素为止。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序的基本原理
冒泡排序的基本思想是:比较相邻的元素,如果第一个比第二个大(升序排序),就交换它们两个;对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数;针对所有的元素重复以上的步骤,除了最后已经排序好的元素。以此类推,直到排序完成。
function bubbleSort($arr) {
$len = count($arr);
for ($i = 0; $i < $len; $i++) {
for ($j = 0; $j < $len - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
// 交换两个元素
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
}
}
}
return $arr;
}
// 示例数组
$exampleArray = [, 34, 25, 12, 22, 11, 90];
// 调用冒泡排序函数
$sortedArray = bubbleSort($exampleArray);
print_r($sortedArray);
冒泡排序的优化技巧
尽管冒泡排序是最简单的排序算法之一,但在实际应用中,它通常不是最高效的。以下是一些优化技巧:
1. 检测是否有交换发生
如果在一次遍历中没有发生任何交换,这意味着数组已经排序完成。因此,我们可以提前结束排序。
function optimizedBubbleSort($arr) {
$len = count($arr);
for ($i = 0; $i < $len; $i++) {
$swapped = false;
for ($j = 0; $j < $len - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
$swapped = true;
}
}
// 如果没有交换,则提前退出
if (!$swapped) {
break;
}
}
return $arr;
}
2. 使用更小的变量存储数组长度
在每次内循环中,我们不需要重新计算数组的长度。可以将它存储在一个变量中,这样可以减少计算量。
function bubbleSortWithLengthVariable($arr) {
$len = count($arr);
for ($i = 0; $i < $len; $i++) {
for ($j = 0; $j < $len - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
}
}
}
return $arr;
}
应用实例
冒泡排序在小型数组或基本操作中非常实用。下面是一个使用冒泡排序来对用户输入的分数进行排序的例子。
// 用户输入的分数
$userScores = [88, 92, 76, 90, 45, 82];
// 使用优化后的冒泡排序函数进行排序
$sortedScores = optimizedBubbleSort($userScores);
print_r($sortedScores);
通过上述例子,我们可以看到冒泡排序虽然不是最优的排序算法,但通过一些简单的优化,它的性能可以得到显著提升。在实际应用中,选择合适的排序算法取决于具体的需求和数据的特性。