冒泡排序

参考文章： 常用排序算法总结(一)

冒泡排序是一种简单的排序算法。顾名思义，就像气泡从水底浮出水面的过程，气泡由小慢慢变大。这个算法的核心就是，比较相邻的两个数，逐渐把较大的数移到最后，从而完成排序。

1.1 算法描述

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复前面3个步骤，直到排序完成。

1.2 动图演示

image

1.3 代码实现

此处我用三种方式去实现，方式一是最常见的方式；方式二是过滤掉原数组中，数字顺序本来就是排好序的情况；方式三是改进版，原来循环一遍，只是把较大的数转移到最后，改进之后，循环一遍先把较大的数转移到最后，然后反过来把较小的数转移到前面。
有兴趣的同学可以具体调试着比较一下，代码中我注释的地方可以打开具体看一下排序的过程。
如果还是看不懂，请联系我！！！咱们好好聊聊。。。

<?php
//输出数组
function echo_arr($arr, $sym=' '){
    echo implode($sym, $arr).'<br>';
}

//交换数字
function swap_item(&$arr, $i, $j){
    $tmp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $tmp;
}

//检测数组
function check_arr($arr){
    if(!is_array($arr)){
        return 'arr error';
    }

    $len = count($arr);
    if($len <= 1){
        return $arr;
    }

    return true;
}

//计算耗时
function time_consuming($start, $end, $name=''){
    $t = $end - $start;
    var_dump($name.'耗时：'.$t);
}

//显示起始时间
function show_time($start, $end, $name=''){
    var_dump($name.' start：'.$start);
    var_dump($name.' end  ：'.$end);
}

//获取乱序的数组
function get_test_arr($len = 200){
    for( $i = 0; $i < $len; $i++ ){
      $arr[] = mt_rand( 1,1000);
    }

    return $arr;
}

//获取顺序的数组
function get_sort_arr($len = 200){
    for( $i = 0; $i < $len; $i++ ){
      $arr[] = $i;
    }

    return $arr;
}

//排序主程序
function bubble_sort($arr){
    $check_re = check_arr($arr);

    if($check_re === true){
        bubble_sort1($arr);
        bubble_sort2($arr);
        bubble_sort3($arr);
    }else{
        echo 'error';
        var_dump($arr);
    }
}

// $arr = [ 6, 4, 7, 2, 9, 8, 1 ];
// $arr = [];
// $arr = '123';

$arr = get_test_arr();
// $arr = get_sort_arr();
echo_arr($arr);
bubble_sort($arr);

//排序方式一
function bubble_sort1($arr){
    $len = count($arr);
    $start = microtime(true);

    for ($j=0; $j < $len-1; $j++) {
        // var_dump($j.'-'.($j+1));
        for ($i=0; $i < $len-1-$j; $i++) { 
            if($arr[$i+1] < $arr[$i]){
                $tmp = $arr[$i];
                $arr[$i] = $arr[$i+1];
                $arr[$i+1] = $tmp;
            }
            // echo_arr($arr);
        }
    }

    $end = microtime(true);
    time_consuming($start, $end, 'bubble_sort-1');
    // echo_arr($arr);
}

//排序方式二
function bubble_sort2($arr){
    $len = count($arr);
    $start = microtime(true);

    $swap = true;
    for ($j=0; $j < $len-1 && $swap; $j++) { 
        // var_dump($j.'-'.($j+1));
        $swap = false;
        for ($i=0; $i < $len-1-$j; $i++) { 
            if($arr[$i+1] < $arr[$i]){
                $tmp = $arr[$i];
                $arr[$i] = $arr[$i+1];
                $arr[$i+1] = $tmp;
                $swap = true;
            }
            // echo_arr($arr);
        }
    }

    $end = microtime(true);

    time_consuming($start, $end, 'bubble_sort-2');
    // show_time($start, $end, 'bubble_sort-2');

    // echo_arr($arr);
}

//排序方式三
function bubble_sort3($arr){
    $start = microtime(true);
    $len = count($arr);
    $swap = true;
    $left = 0;
    $right = $len-1;

    while ($left < $right && $swap) { 
        $swap = false;
        for ($i=$left; $i < $right-$left; $i++) { 
            // var_dump($i.'/'.($i+1).'/'.$swap);
            if($arr[$i+1] < $arr[$i]){
                $tmp = $arr[$i];
                $arr[$i] = $arr[$i+1];
                $arr[$i+1] = $tmp;
                $swap = true;
            }
            // echo_arr($arr);
        }
        $right--;
        
        if(!$swap){
            continue;
        }

        for ($i=$right; $i > $left; $i--) { 
            // var_dump($i.'/'.($i-1));
            if($arr[$i] < $arr[$i-1]){
                $tmp = $arr[$i];
                $arr[$i] = $arr[$i-1];
                $arr[$i-1] = $tmp;
                $swap = true;
            }
            // echo_arr($arr, '-');
        }
        $left++;
    }

    $end = microtime(true);

    time_consuming($start, $end, 'bubble_sort-3');
    // show_time($start, $end, 'bubble_sort-3');

    // echo_arr($arr);
}

image.png

上图是我取了一个200个数的数组排序之后的结果，可以看到三比方式一要快一些。