排序算法之冒泡排序

根据时间复杂度的不同，主流的排序算法可以分为3大类。

1. 时间复杂度为O(n2)的排序算法
   冒泡排序
   选择排序
   插入排序
   希尔排序（希尔排序比较特殊，它的性能略优于O(n2)，但又比不上O(nlogn)，姑且把它归入本类）
2. 时间复杂度为O(nlogn)的排序算法
   快速排序
   归并排序
   堆排序
3. 时间复杂度为线性的排序算法
   计数排序
   桶排序
   基数排序

冒泡排序

按照冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。

image.png

这时，冒泡排序的第1轮就结束了。数列最右侧元素9的位置可以认为是一个有序区域，有序区域目前只有1个元素。

image.png
image.png
image.png

具体代码实现：

class Code{
    
    function sort($arr){
        $intLength = count($arr);
        //外层循环用于缩短冒泡匹配距离，最右端不再匹配
        for($i=0;$i<$intLength-1;$i++){
            //内层循环用于冒泡，比较相邻的两个元素
            //减去$i就是缩短了数据冒泡距离，每次求出当前冒泡的最大值放在右侧
            for($j=0;$j<$intLength-$i-1;$j++){
                if($arr[$j]>$arr[$j+1]){
                    //因$arr[$j]马上要重新赋值，所以先将其值暂存
                    $tmp = $arr[$j];
                    $arr[$j] = $arr[$j+1];
                    $arr[$j+1] = $tmp;
                }
            }
        }
        return $arr;
    }

    //运行
    function run(){
        $arr = array(8,5,7,4,2,0,1,3,9);
        $arrNew = $this->sort($arr);
        print_r($arrNew);
    }
    
}
$obj = new Code();
$obj->run();

冒泡排序优化

class Code{
    
    function sort($arr){
        $intLength = count($arr);
        //外层循环用于缩短冒泡匹配距离，最右端不再匹配
        for($i=0;$i<$intLength-1;$i++){
            //预先设定数组为有序
            $isSort = true;
            //内层循环用于冒泡，比较相邻的两个元素
            //减去$i就是缩短了数据冒泡距离，每次求出当前冒泡的最大值放在右侧
            for($j=0;$j<$intLength-$i-1;$j++){
                if($arr[$j]>$arr[$j+1]){
                    //因$arr[$j]马上要重新赋值，所以先将其值暂存
                    $tmp = $arr[$j];
                    $arr[$j] = $arr[$j+1];
                    $arr[$j+1] = $tmp;
                    //当出现交换的时候，则表示数组为非有序
                    $isSort = false;
                }
            }
            //冒泡过程未出现交换，则表示已是有序了，跳出循环
            if($isSort){
                break;
            }
        }
        return $arr;
    }

    //运行
    function run(){
        $arr = array(8,5,7,4,2,0,1,3,9);
        $arrNew = $this->sort($arr);
        print_r($arrNew);
    }
    
}
$obj = new Code();
$obj->run();

冒泡排序的进一步优化
思路：通过设定无序数列边界的方法，减小循环数

class Code{
    
    function sort($arr){
        $intLength = count($arr);
        //记录最后一次交换的位置
        $lastExchangeIndex = 0;
        //无序数列的边界
        $sortBorder = $intLength-1;
        //外层循环用于缩短冒泡匹配距离，最右端不再匹配
        for($i=0;$i<$intLength-1;$i++){
            //预先设定数组为有序
            $isSort = true;
            //内层循环用于冒泡，比较相邻的两个元素
            //减去$i就是缩短了数据冒泡距离，每次求出当前冒泡的最大值放在右侧
            for($j=0;$j<$sortBorder;$j++){
                if($arr[$j]>$arr[$j+1]){
                    //因$arr[$j]马上要重新赋值，所以先将其值暂存
                    $tmp = $arr[$j];
                    $arr[$j] = $arr[$j+1];
                    $arr[$j+1] = $tmp;
                    //当出现交换的时候，则表示数组为非有序
                    $isSort = false;
                    //记录最后一次交换的位置
                    $lastExchangeIndex = $j;
                }
            }
            //更新无序数列的边界
            $sortBorder = $lastExchangeIndex;
            //冒泡过程未出现交换，则表示已是有序了，跳出循环
            if($isSort){
                break;
            }
        }
        return $arr;
    }

    //运行
    function run(){
        $arr = array(8,5,7,4,2,0,1,3,9);
        $arrNew = $this->sort($arr);
        print_r($arrNew);
    }
    
}
$obj = new Code();
$obj->run();

输出结果：

image.png