话说，从acm开始，除了刚刚开始的时候写过几次冒泡和选择排序，之后便被TLE弄乖了，转投sort怀抱。

　　不过，很多时候，不再去追求那种极速的时候，去改进一个算法也是很有趣的事情。

　　你会说，理解这些有意义么？能比得过快排么？

　　我想说，我们所追逐的就是一种过程，是对这种思路的更进一步的理解，也许，会有意外发现。

　　

　　话不多说，先放上最朴素的冒泡（以下排序的结果一律从小到大）：

　　1.从第一个元素开始，与之后相邻的比较，若反序，则交换，这样，一次循环之后，最后一个数一定是最大的，就像泡泡一样，大的慢慢升上来了。

　　2.重复上述操作，直到n-1次操作之后，整个序就排好了。

　　

//冒泡排序1void Bubble_1(int a[], int n){       int i, j;       for (i = 0; i < n; i++)              for (j = 1; j < n - i; j++)//这里稍微优化一点，书上写的实在不能看                     if (a[j - 1] > a[j])                            Swap(a[j - 1], a[j]);}

 

　　优化一：非常常见的优化，加上一个flag，当有一趟没有交换的时候，表示已经有序了——课本也就到此为止了，但真的就到这为止了么？

　　优化二：对步骤一，从前往后一趟，第二趟从后往前循环，之后再从前往后一趟，如此往复循环，这样可以极大的提高冒泡的稳定性，比如（2,3,4,5,……,n,1）。

　　优化三：假设，有100个数，后面80个数全部有序并且最小的一个大于前面20个数中的任意一个，我们可以进一步的优化flag的意义，这里flag为最后一次交换的　　　　　　　位置，这样，针对上面的情况或者中途变化成类似的情况，执行次数大大减少。很开心的是，这三个优化中，第三个是第一个的升级，而第二个可以和第　　　　　　　三个结合在一起，形成更有效的方法

　　优化四：这样想一下，如果以一个点为标准，比他大的放右边，比他小的放左边，这样就能同时冒多个泡泡（比这个大的一次性全部冒到他的右边，小的也一次性

　　　　　　冒到左边）。再对左边和右边进行分治，重复操作，就能非常快的得到一个有序列了——咦，是不是很熟悉，对了，这就是快排！！！

　　

　　这就是乐趣，万变不离其宗，现在你还小看冒泡么？