算法—冒泡排序

冒泡排序介绍

冒泡排序（Bubble Sort）
它是中较简单的排序算法。它会遍历若干次要排序的数组，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换他们的位置，这样一次遍历之后，最大的元素就在数组的末尾。采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数组都排好序为止。

冒泡排序的时间复杂度

冒泡排序的时间复杂度是O(N^2)

冒泡排序的稳定性

冒泡排序是稳定的算法，它满足稳定算法的定义

算法的稳定性：假设在数列中存在a[i] = a[j], 若在排序之前,a[i]在a[j]前面，并且在排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的

PHP代码实现

// 第一种实现
$arr = [23, 4, 65, 1, 3, 99, 10];
BubbleSort($arr);

var_dump($arr);

// 冒泡排序
function BubbleSort(&$arr) {
    for ($i = sizeof($arr) - 1; $i > 0; $i--) {
        for ($j = 0; $j < $i; $j++) {
            if ($arr[$j] > $arr[$j+1]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $tmp;
            }
        }
    }
}


/**
    23  4   65  1   3   99  10

1)  4   23  65  1   3   99  10      i = 6, j = 0 
    4   23  65  1   3   99  10      i = 6, j = 1 
    4   23  1   65  3   99  10      i = 6, j = 2
    4   23  1   3   65  99  10
    4   23  1   3   65  10  99

2)  4   23  1   3   65  10  99      i = 5, j = 0
    4   1   23  3   65  10  99      i = 5, j = 1 
    4   1   3   23  65  10  99
    4   1   3   23  10  65  99

3)  1   4   3   23  10  65  99
    1   3   4   23  10  65  99
    1   3   4   10  23  65  99
 */

// 第二种实现
// 对于一个长度为N的数组，我们需要排序 N-1 轮，每 i 轮 要比较 N-i 次。
// 对此我们可以用双重循环语句，外层循环控制循环轮次，内层循环控制每轮的比较次数

function BubbleSort2(&$arr) {
    $len = sizeof($arr);
    // 外层控制循环次数
    for ($i=1; $i < $len; $i++) {
        // 内存控制每轮比较次数
        for ($j=1; $j < $len-$i; $j++) { 
            $tmp = $arr[$j];
            $arr[$j] = $arr[$j+1];
            $arr[$j+1] = $tmp;
        }
    }
}