【七类排序】之第一种：冒泡排序

序

    鄙农近来温习算法，苦于思维渐钝，脑力不佳，杂念繁多。唏嘘不复年幼时一目十行而皆了然于心之勇。故撰此文以记之，望与有志之士共同研讨参悟。

注：本文若无特殊说明， 一切排序都以递增为最终目的。

冒泡排序（bubble sort）是最基本的排序方法，任何一本编程教材都要涉及的内容。其思想可以概括为一句话： 如果前边的数大于后边的数，那么交换其顺序。


具体步骤：假设数组有N个元素，下标从0到N-1
step 1： 对数组元素从0至N-1进行遍历， 若第i-1个元素大于第i个， 则交换元素i-1与元素i的顺序，其中0<i<N。显然， 此过程完毕后， 最大的元素将位列第N-1个.
step 2:  对数组元素从0至N-2进行遍历， 其余操作同step1, 完毕后， 第2大元素将位列第N-2个.
......
step N-1: 对数组元素从0至1进行遍历，其余操作相同。 完毕后， 第N-1大元素将位列数组第1个， 那么数组第0个一定是最小的元素。

该排序时间复杂度为n^2, 实现非常简单，设数组为a， 核心部分为

for (int i=0; i<N; i++)
    for (int j=1; j<N-i; j++)
         if (a[j-1]<a[j]) swap(a[j],a[j-1]);

其中， 第二层循环j每次循环一趟后， 都会将第i+1大的元素交换至数组的第N-(i+1)个位置上,是不是特别像泡泡一个个往上冒？ 故因此得名。

优化1： 若在某一次j循环中， 未发生任何交换动作，说明该数组已经有序。

那么我们设定一个标志flag. 若该次遍历发生了交换， 则flag=true, 否则， flag=false,排序完毕。
代码核心部分实现如下：
bool flag=true;
int i=N;
    while (flag)
    {
        flag = false;
        for (int j=1; j<i; j++)
             if (a[j-1]<a[j]) {
                 swap(a[j],a[j-1]);

                 flag = true;
             }
        i--;
     }

优化2：我们设想， 若有一个长度为m的数组， 而其只有前n个元素无序， 第n+1到第m个是有序的， 若m>>n， 我们只需要处理前n个即可。

在这种情况下， 每一次遍历都记录最后一次发生交换元素动作的位置， 那么下一次遍历只需要到这个位置即可， 因为该位置以后的元素都已经有序。
代码核心部分实现如下：
int flag=n;

while (flag>0) {
     int k=flag;
     flag=0;
     for (int j=1; j<k; j++)
          if (a[j-1]>a[j]) {
             flag = j;
             swap(a[j-1],a[j]);
          }
}

总结：以上两种优化都是基于对冒泡排序算法的原理进行的细节加工，不管怎么优化， 还是摆脱不了老爷车的事实。对于该算法， 了解其原理即可~

以前看过一篇抨击冒泡法的文章，意思就是冒泡法效率如此低，为什么总是在大学里的入门级CS课程中出现

孤笑客 发表于 2012-11-26 05:50
以前看过一篇抨击冒泡法的文章，意思就是冒泡法效率如此低，为什么总是在大学里的入门级CS课程中出现

我的理解是还是要体现一种“交换”的实现手段。

其实快排也是如此， 设定一个阈值， 小于该阈值的沉下去， 大于的冒泡上来，然后套上二分解决的框架。

冒泡是我第一个学习的算法，它体现的哲理和所折射出的算法的神秘让当年的我为之深深地着迷，我对它怀有特殊的感情

学的第一种算法啊，哈哈~~

JAGUAR 发表于 2012-11-26 14:21
冒泡是我第一个学习的算法，它体现的哲理和所折射出的算法的神秘让当年的我为之深深地着迷，我对它怀有特殊 ...

能不能详细讲讲你所体会到的哲学？好奇中。

加入一段java实现的代码吧。
private ArrayList<Integer> BubbleSort(ArrayList<Integer> array){
                for(int i=0;i<array.size();i++){
                        for(int j=0;j<array.size()-1-i;j++){
                                if(array.get(j) > array.get(j+1)){
                                        Collections.swap(array, j+1, j);
                                }
                        }
                }
                return array;
        }
       

也是我学过的第一个算法