冒泡排序

原理:
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);

 



Tagged , . Bookmark the permalink.

Comments are closed.