最近在复习数据结构，就写一写博客来记录一下自己学习的路程。

一、冒泡排序很形象的就是最小的数字不断往上冒泡，每冒泡一次最上面的数字就是最小的，这个过程很像在水里冒泡一样，所以就叫冒泡算法。

如上图所示，这是经过了一次冒泡之后，2的位置从4变化到了1。所谓冒泡排序，最主要的思想就是两两比较，大的在下面小的在上面，这个过程也就是冒泡的过程。之后的冒泡过程也类似。经过6次冒泡，则成功将上面的集合变成有序集合。以下我用PHP代码来实现一下（为啥用PHP，因为我坚信PHP是世界上最好的语言~~~有点没底气哈哈哈哈）

代码1：

<?php

function maopao(&$list)
{

    $count = count($list);
    for ($i = 0; $i < $count; $i++) { //每循环一次就是一次冒泡的过程
        for ($j = $count – 1; $j > $i; $j–) {
            if ($list[$j – 1] > $list[$j]) {
                swap($list[$j – 1], $list[$j]);
            }
        }
    }
}
function swap(&$one, &$two)
{
    $tmp = $one;
    $one = $two;
    $two = $tmp;
}

?>

输入：输入一个数组集合 （不考虑非法输入）  输出：一个有序的数组

 

优化:我们仔细想一下，如果要排序的集合本身就比较有序，那冒泡排序算法是不是依然进行n次冒泡进行比较，只是不交换数据而已，这样子的话就做了很多无用功，我们是不是可以考虑在数据不交换的时候就停止比较了呢？因此，我们可以考虑添加一个标志位，在进行比较的时候如果不交换数据就置为true，这样就可以控制在数据不交换的时候就不进行比较了。以下是PHP实现

代码2：

<?php

function maopao(&$list)
{

   $count = count($list);

    static $flag = true;
    for ($i = 0; $i < $count && $flag; $i++) { //每循环一次就是一次冒泡的过程

        $flag = false;
        for ($j = $count – 1; $j > $i; $j–) {
            if ($list[$j – 1] > $list[$j]) {
                swap($list[$j – 1], $list[$j]);

                $flag = true;
            }
        }
    }
    return $list;
}
function swap(&$one, &$two)
{
    $tmp = $one;
    $one = $two;
    $two = $tmp;
}

?>

只要添加一个标志位来判断它是否已经有序了，是否需要继续冒泡，就可以减少不必要的比较，在性能方面还是提升了不少。这种性能在数据量比较大的时候还是能够体现出来的。

时间复杂度：最好的情况下（在集合本身已经有序的情况下）冒泡排序只需要比较n-1次即可

最坏的情况下（在集合本身完全逆序的情况下）冒泡排序需要比较1+2+3+4+....n-1=n*(n-1)/2次

所以冒泡排序的时间复杂度为O（n²），排序是稳定的

总结

冒泡排序很形象地就是小的数字不断往上冒泡，最主要的思想就是两两交换，大的往下沉小的往上冒泡，每次冒泡最小的数字都冒泡到顶端。考虑到集合本身有序的情况，可以将有序之后做一些标识停止冒泡，这样可以提升效率。