冒泡排序算法

冒泡排序 作为一种渐进复杂度O(N^2)的排序方法, 实质上属于一种形式“玄妙的”选择排序,只是相比选择排序多了一些无意义的交换。它比选择排序更难于理解和解释(就在于它多次无意义的交换的干扰,不信你讲给楼下阿姨比较下),又不具有插入排序的“在线”优点,跟极易理解的基数排序更不能在思维难度上相比,就算同快排,归并相比,也具有复杂度高得多的劣势。那么为什么冒泡排序会作为经典,成为初学者学习语言的遇到的首个算法?



int temp;
            int[] arrSort = new int[] { 10, 8, 3, 5, 6, 7, 9 };
            for (int i = 0; i < arrSort.Length; i++)
            {
                for (int j = i + 1; j < arrSort.Length; j++)
                {
                    if (arrSort[j] < arrSort[i])
                    {
                        temp = arrSort[j];
                        arrSort[j] = arrSort[i];
                        arrSort[i] = temp;
                    }
                }
}


冒泡排序并不是一种有工程意义的排序算法。不如说std::sort以外的也许都没有工程意义……
但是讲冒泡排序可以带出几个问题:

  1. 冒泡排序只有一个基本操作就是比较和交换相邻的两个元素,可以体现将一个复杂的问题转化为非常简单的操作的叠加的思想

  2. 冒泡排序看上去每一次循环都差不多,为什么可以在有限次循环之内结束,如何分析算法的正确性,这是一个不错的数学问题

  3. 分析复杂度简单,一眼就看得出来是O(n^2)。代码也的确是最短的。边界条件很少。甚至于多循环几遍问题也不大。

  4. 分析完冒泡排序会发现,其他O(n^2)的算法的原理都跟冒泡排序有共通之处:用O(n)的时间排出一个元素。所以讲其他O(n^2)排序就不用花太多时间解释了。

嘛其实哪个都不是什么关键问题,其实也许最大的原因是因为这么讲没啥毛病,所以也没必要改吧……对于初学者来说,写一个冒泡排序写对的概率其实要比其他O(n^2)的算法高不少。


另外冒泡排序有个小优点是很容易展开成没有循环的形式,而且代码也不会太难看,比如说我现在固定要排的是四个数,就可以写:

#define cs(a,b) (if(a>b){int t; t = a; a = b; b = t;})
cs(a,b);cs(b,c);cs(c,d);cs(a,b);cs(b,c);cs(a,b);

用别的排序就不太可能了。虽然现在编译器都可以自动循环展开了,但以前并不是这样,而且这样小清新的代码多好啊