PHP – 冒泡排序 – 老迟笔记

一、概述

冒泡排序，顾名思义就是整个过程就像冒泡一样往上升。

　
基本思想：

　　对于给定的 n 个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，则交换两个记录的位置。

　　进行一轮比较和换位后，n个记录中的最大记录将位于第 n 位。

　　然后对前（n-1）个记录进行第二轮比较，重复该过程直到进行比较的记录只剩下一个时为止。

　
算法原理：

（1）从第一个元素开始，比较相邻的两个元素，如果前一个比后一个大，则交换这两个元素的位置。

（2）不论第一个元素和第二个元素是否交换了位置，我们都继续比较当前数组的第二个元素和第三个元素。

（3）继续比较当前数组的第三个元素和第四个元素

（4）直到比较到最后一个元素

（5）该轮结束，继续下一轮比较（重复第1步到第4步）

二、代码实现：

<?php
declare(strict_types = 1);

class TestCase
{
    /**
     * 冒泡排序
     *
     * @param array $array
     * @return array
     */
    public static function sortArray(array $array) : array
    {
        $arrayLen = count($array);
        // 控制排序轮次
        for ($i = 1; $i < $arrayLen; $i++) {
            // 控制某一轮的比较次数
            for ($k = 0; $k < $arrayLen - $i; $k++) {
                if ($array[$k] > $array[$k + 1]) {
                    $tmp = $array[$k + 1];
                    $array[$k + 1] = $array[$k];
                    $array[$k] = $tmp;
                }
            }
        }
        return $array;
    }
}

// 需要排序数组
$arr = [20, 19, 15, 36, 22, 3, 77, 95, 64, 15, 24, 36];
// 执行排序
$arr = TestCase::sortArray($arr);
// 输出结果
foreach ($arr as $v) {
    echo $v . ' ';
}

显示结果：

3 15 15 19 20 22 24 36 36 64 77 95

三、改进版

　　在传统冒泡排序的基础上，通过设置一个标志bool，用于记录每轮排序中最后一次交换的位置。由于bool之后的记录均已交换到位，因此下一轮排序时只要扫描到bool位置即可，不需要再对bool之后的循环排序。

<?php
declare(strict_types = 1);

class TestCase
{
    /**
     * 冒泡排序
     *
     * @param array $array
     * @return array
     */
    public static function sortArray(array $array) : array
    {
        $i = count($array) - 1;
        while ($i > 0) {
            $bool = 0;
            for ($k = 0; $k < $i; $k++) {
                if ($array[$k] > $array[$k + 1]) {
                    $bool = $k;
                    $tmp = $array[$k];
                    $array[$k] = $array[$k + 1];
                    $array[$k + 1] = $tmp;
                }
            }
            $i = $bool;
        }
        return $array;
    }
}

// 需要排序数组
$arr = [20, 19, 15, 36, 22, 3, 77, 95, 64, 15, 24, 36];
// 执行排序
$arr = TestCase::sortArray($arr);
// 输出结果
foreach ($arr as $v) {
    echo $v . ' ';
}

经测试，改进版比正统版循环次数少了一些，内存消耗相差不大，说明改进成功。

打赏赞