php实现冒泡排序算法

理解

冒泡排序，时间复杂度哦、O(N^2)
冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是 O(N 2)。这是一个非常高的时间复杂度。冒泡排序早在 1956 年就有人开始研究，之后有很多人都尝试过对冒泡排序进行改进，但结果却令人失望。如 Donald E. Knuth（中文名为高德纳， 1974 年图灵奖获得者）所说：“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外，似乎没有什么值得推荐的。”

代码实现

<?php
    public function sort_test()
    {
        $array_old = [];
        for ($i = 0; $i < 1000; $i++) {
            $array_old[] = rand(0, 99999);
        }
        $time_1    = $this->msectime();
        $array_new = $this->maopao_sort_1($array_old);
        $time_2    = $this->msectime();
        echo "冒泡排序第一个版本执行时间" . ($time_2 - $time_1) . '    ';
        $time_2    = $this->msectime();
        $array_new = $this->maopao_sort_2($array_old);
        $time_3    = $this->msectime();
        echo "冒泡排序第二个版本执行时间" . ($time_3 - $time_2) . '    ';
        $time_3    = $this->msectime();
        $array_new = $this->maopao_sort_3($array_old);
        $time_4    = $this->msectime();
        echo "冒泡排序第三个版本执行时间" . ($time_4 - $time_3) . '    ';
        $this->success($array_new);
    }

    public function maopao_sort_1($array)
    {
        $len = count($array);
        for ($i = 0; $i < $len - 1; $i++) {
            for ($j = 0; $j < $len - $i - 1; $j++) {
                if ($array[$j] > $array[$j + 1]) {
                    $temp          = $array[$j + 1];
                    $array[$j + 1] = $array[$j];
                    $array[$j]     = $temp;
                }
            }
        }
        return $array;
    }

    public function maopao_sort_2($array)
    {
        $len = count($array);
        for ($i = 0; $i < $len - 1; $i++) {
            $is_sort = true;
            for ($j = 0; $j < $len - $i - 1; $j++) {
                if ($array[$j] > $array[$j + 1]) {
                    $temp          = $array[$j + 1];
                    $array[$j + 1] = $array[$j];
                    $array[$j]     = $temp;
                    $is_sort       = false;
                }
            }
            if ($is_sort) {
                break;
            }
        }
        return $array;
    }

    public function maopao_sort_3($array)
    {
        $sort_border = count($array) - 1;
        $sort_index  = 0;
        for ($i = 0; $i < count($array) - 1; $i++) {
            $is_sort = true;
            for ($j = 0; $j < $sort_border; $j++) {
                if ($array[$j] > $array[$j + 1]) {
                    $temp          = $array[$j + 1];
                    $array[$j + 1] = $array[$j];
                    $array[$j]     = $temp;
                    //不是有序的，标记为false
                    $is_sort = false;
                    //更新最后一次交换元素的位置
                    $sort_index = $j;
                }
            }
            //下一次循环结束位置
            $sort_border = $sort_index;
            if ($is_sort) {
                break;
            }
        }
        return $array;
    }


    public function msectime()
    {
        list($msec, $sec) = explode(' ', microtime());
        $msectime = (float)sprintf('%.0f', (floatval($msec) + floatval($sec)) * 1000);
        return $msectime;
    }
?>

测试结果

image.png