什么是冒泡排序
冒泡排序的英文Bubble Sort，是一种最基础的交换排序。
大家一定都喝过汽水，汽水中常常有许多小小的气泡，哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻，所以小气泡可以一点一点向上浮动。
冒泡排序的排序过程就和小气泡一样,每次排序都将最大的数往上冒.下一轮排序再将第二大的数往上冒,依次往复.
function bubble($arr)
{
if (!$arr) {
return [];
}
$len = count($arr);
for ($i = 0; $i < $len; $i++) {
for ($j = 0; $j < $len - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
$tmp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $tmp;
}
}
}
return $arr;
}
$arr = [1, 5, 9, 100, 100, 50, 60, 102, 103];
$arr = bubble($arr);
print_r($arr);//1,5,9,50,60,100,102,103
进一步优化
我们假设经过前面5轮的排序,数组已经是有序序列
$arr = [1,5,9,50,60,100,100,102,103];
后面的3轮排序是多余的,没必要的.
function bubble($arr)
{
if (!$arr) {
return [];
}
$len = count($arr);
for ($i = 0; $i < $len; $i++) {
//有序标记，每一轮的初始是true
$sorted = true;
for ($j = 0; $j < $len - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
$tmp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $tmp;
//数组元素发生了交换,说明是无序的
$sorted = false;
}
}
//数组是有序的,之后的循环没有必要执行
if ($sorted) {
break;
}
}
return $arr;
}
$arr = [1, 5, 9, 100, 100, 50, 60, 102, 103];
$arr = bubble($arr);
print_r($arr);//1,5,9,50,60,100,102,103
再进一步优化
待排序数组可以分成无序区和有序区,上述的每轮循环会冒出一个数组元素放在有序区.无序区的数组元素都需要互相比较大小,找到最大的一个数.
但是有可能无序区的后几位已经是有序的,就没必要再相互比较了, 换言之,有序区比想象中的要大, 那就白白进行了多次不必要的比较.
function bubble($arr)
{
if (!$arr) {
return [];
}
$len = count($arr);
//最后一次发生交换的数组下标
$lastIndex = 0;
//有序区的边界
$border = $len - 1;
for ($i = 0; $i < $len; $i++) {
$sorted = true;
for ($j = 0; $j < $border; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
$tmp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $tmp;
$sorted = false;
//发生交换的数组下标就是$j
$lastIndex = $j;
}
}
//有序区的边界
$border = $lastIndex;
if ($sorted) {
break;
}
}
return $arr;
}
$arr = [1, 5, 9, 100, 100, 50, 60, 102, 103];
$arr = bubble($arr);
print_r($arr);//1,5,9,50,60,100,102,103
