愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

冒泡排序算法的优化

今天我们要来谈一种算法,是的,你没有看错,就是“冒泡排序”,这是最基本最初级的一个算法,然而,尽管冒泡排序很初级,却也有优化的空间

我们采用PHP来描述这个算法,最基本的冒泡排序,是这样子的:

function bubbleSort(&$arr) {
    $n = count($arr);
    for($i=1; $i<=$n; $i++) {
        for($j=$n-1; $j>=$i; $j--) {
            if($arr[$j] < $arr[$j-1]) {
                swap($arr[$j], $arr[$j-1]);
            }
        }
    }
}

这是最基本的冒泡排序,相信学过《算法与数据结构》的你并不会陌生,现在,我们想对这个算法进行进一步的改进。

想一想,如果我们某一趟比较后,发现没有元素发生了交换,是不是代表说这个数组已经有序了?
那么这样子的情况下,我们可以用一个flag变量来标记数组中在某一趟中是否有元素发生过交换,如果没有的话,说明已经排序完成。
初步改进后,算法是长这样子的:

function bubbleSort(&$arr) {
    $n = count($arr);
    $flag = false;
    for($i=1; $i<$n; $i++) {
        for($j=$n-1; $j>=$i; $j--) {
            if($arr[$j] < $arr[$j-1]) {
                swap($arr[$j], $arr[$j-1]);
                $flag = true;
            }
        }

        if(!$flag) break;
    }
}

现在,我们考虑到待排序的数组是下面这么一种情况:
arr:1、2、3、9、4、7
按照冒泡排序的基本思想,每一次比较都要将较轻(小)的元素进行交换,从而在每一趟比较后,最小的那个元素都会被放置在最前面。在完成n-1趟排序后,数组就是有序的了。但是,正如上诉的情况,我们可以看到1、2、3已经是有序的了,采用普通冒泡算法的时候,仍然会在排序未完成前,进行3和2比大小,2和1比大小这两部没有必要的比较。因此,这里正是我们能够优化的地方。
现在,以上面的数组为例,模拟下排序的过程:

  • 第一趟比较后得:1、2、3、4、9、7,发生交换的时候:$j=4=$pos
  • 第二趟比较后得:1、2、3、4、7、9,发生交换的时候:$j=5=$pos
  • 第三趟比较后得:1、2、3、4、7、9,没有发生交换
    ……

我们可以发现,除了第一趟和第二趟是有必要的话,后面的几趟都没有必要了。
如果在一趟中的最后一次交换发生在$pos,那么说明$arr[

那么,什么时候可以终止比较呢?我们可以从上面看出,第三趟的时候,已经没有发生交换了,也就是上一趟的$pos值在这一趟里仍然一样,这时候就可以终止比较了。故我们给出最终的优化版本:

function bubbleSort(&$arr) {
    $n = count($arr);
    $lastPos = $pos = 0;
    for($i=1; $i<$n; $i++) {
        $lastPos = $pos;
        for($j=$n-1; $j>$lastPos; $j--) {
            if($a[$j] < $a[$j-1]) {
                swap($a[$j], $a[$j-1]);
                $pos = $j;
            }

            if($lastPost == $pos) break;
        }
    }
}

接下来,我们要来做个性能测试,检验一下改进后的冒泡排序算法是否能够真的提高排序效率。经过实际测试,测试结果为:

10000个(50%有序数据):
(普通冒泡)循环次数:49995000 Time Used: 11.580069065094
(改进冒泡)循环次数:13100871 Time Used: 3.8322710990906

10000个(无序随机数据):
(普通冒泡)循环次数:49995000 Time Used: 14.335252046585
(改进冒泡)循环次数:49930601 Time Used: 15.203200101852

可以看出,在有较多有序数据的时候,改进冒泡的性能提升效果是显著的(因为直接大幅度减小了循环的次数)
但是,在无序数据较多的时候,改进冒泡不仅没有提升性能,甚至于还比普通冒泡慢。但是我们发现改进冒泡仍然减少了循环的次数,之所以排序时间比较久,应该和改进冒泡多增的语句耗时有关。

因此,我们得出结论:若一组数据里,含有较多的有序数据,那么使用改进冒泡对于性能的提升是显著的。如果数据较为无序,则未必能够提升性能,反而会多出额外的开销。虽然冒泡排序是简单的排序算法,但是我们知道在某些特定情况下,简单排序算法仍然有它的应用场景,而本次对冒泡排序算法的改进研究所运用的思想,仍然是有帮助的。