10大经典排序算法之冒泡排序(PHP版)

发布时间:2020/11/20 作者:天马行空 阅读(189)

冒泡排序,是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小(大)的元素会经由交换慢慢"浮"到数列的顶端。


算法步骤
1、假如数组有n个值,那么就进行n-1轮冒泡,因为进行到第n轮的时候就只有一个元素了,所以不需要执行第n轮;
2、每轮都从第一个元素开始和后面一个元素进行比较,如果比后面一个元素的值小(大)就和后面一个进行交换,那么单轮比较完之后,最后的那个元素就是最小(大)的,每轮冒泡(数组总长度-轮次)次。


动图演示

bubbleSort.gif


代码实现:

public function bubbleSort(array $arr)
{
    $length = count($arr);
    
    for ($i = 0; $i < $length - 1; $i ++) { // 进行$length-1轮冒泡
        
        $flag = false; // 记录当轮冒泡是否发生了交换
        
        for ($j = 0; $j < $length - $i - 1; $j ++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $tmp;
                $flag = true;
            }
        }
        
        if ($flag == false) { // 优化执行效率
            break; // 这一轮冒泡完都没有发生交换的话,那么说明已经不需要进行下一轮冒泡了,直接跳出
        }
    }
    
    return $arr;
}



关键字php 算法