原理: 1、比较相邻的元素。如果第一个比第二个大(小),就交换他们两个。 2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大(小)的数。 3、针对所有的元素重复以上的步骤,除了最后一个。 4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较 分析: 最好的时间复杂度为O(n),最坏的时间复杂度为O(n2) 稳定性: 属于稳定性排序
示例:
<?php
//冒泡排序
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$num = count($arr);
$total = 0;
for($i = 0; $i < $num; $i++) {
for($j = 0; $j < $num - $i - 1; $j++){ $total++; if($arr[$j] > $arr[$j+1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $temp;
}
}
}
echo $total;//66次循环
print_r($arr);
优化:
如果内层循环没有进行交互则表示已经排序完成
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$total = 0;
$num = count($arr);
$break = false;
for($i = 0; $i < $num; $i++) {
$break = true;
for($j = 0; $j < $num - $i - 1; $j++){ $total++; if($arr[$j] > $arr[$j+1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $temp;
$break = false;
}
}
if($break) {
break;
}
}
echo $total;//45次循环
print_r($arr);
//优化第二步
//缩减内层循环排序区间,如果0到i的位置是有序,那么上次循环区间是i到n
//交换的位置在i到n之间的pos位置
//其中可以知道i到pos的位置是有序的,那么下次循环就可以从post到n
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$num = count($arr);
$total = 0;
$break = false;
$lastSwapPos = $lastSwap = 0;
for($i = 0; $i < $num - 1; $i++) { $lastSwap = $lastSwapPos; for($j = $num - 1; $j > $lastSwap; $j--){
$total++;
if($arr[$j - 1] > $arr[$j]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j - 1];
$arr[$j - 1] = $temp;
$lastSwapPos = $j;
}
}
if($lastSwap == $lastSwapPos) {
break;
}
}
echo $total;//39次循环
print_r($arr);
//双向冒泡(鸡尾酒排序)
/*
原理
数组中的数字本是无规律的排放,先找到最小的数字,把他放到第一位,然后找到最大的数字放到最后一位。
然后再找到第二小的数字放到第二位,再找到第二大的数字放到倒数第二位。以此类推,直到完成排序
*/
//冒泡排序
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$num = count($arr);
$total = 0;
$left = 0;
$right = $num - 1;
while ($left < $right) {
$l = $left + 1;
$r = $right - 1;
for($i = $left; $i < $right; $i++) {
$total++;
if($arr[$i] > $arr[$i+1]) {
$temp1 = $arr[$i];
$arr[$i] = $arr[$i+1];
$arr[$i+1] = $temp1;
$r = $i;
}
}
$right = $r;
for($j = $right;$j > $left; $j--) {
$total++;
if($arr[$j] < $arr[$j - 1]) {
$temp2 = $arr[$j-1];
$arr[$j - 1] = $arr[$j];
$arr[$j] = $temp2;
$l = $j;
}
}
$left = $l;
}
echo $total;//30次循环
print_r($arr);