冒泡排序(Bubble Sort)
LanyuanXiaoyao's Blog ヽ(✿゚▽゚)ノ

冒泡排序(Bubble Sort)

2017-03-09

概念

冒泡排序是一种简单的排序算法.基本思想是迭代地对数列中的第一个元素到最后一个元素进行两两比较,当需要的时候交换这两个元素(位置).重复这个过程一直到所有元素都被排序到正确的位置上.
冒泡排序得名于较小的元素如同”气泡”一样逐渐漂浮到数列的顶端.

步骤

  1. 比较相邻的元素,如果第一个比第二个大1,就交换它们两个的位置.
  2. 对每一对相邻元素作进行同样的步骤,从开始第一对到结尾的最后一对这步做完后.
  3. 进行一轮的比较之后,最大的数会被不断交换到最后一位,这样最后一位数就是有序2的了.
  4. 针对所有的元素重复以上的步骤,直到所有的元素都被排好序.

举例

例 1

假定有一个数组[5, 7, 4, 10, 9],我们要把这个数组按从小到大排列

  1. 我们从第一个数开始,两个一组进行比较大小,也就是把第一个数和第二个数比较,如果:
    • 第一个数比第二个数大,那么把这两个数交换
    • 第一个数比第二个数小,那么不进行任何操作
  2. 在这个例子当中,57要小,那么我们不进行任何操作,然后开始比较下一组数,也就是第二数个和第三个数比较。
  3. 还是同样的比较方法,这个时候,我们发现74大,那么我们就交换这两个数的位置,数组就变成了[5, 4, 7, 10, 9]
  4. 然后开始比较第三个数和第四个数,依次类推……
  5. 当我们比较完最后的两个数的时候,第一轮比较就已经完成了,我们可以发现,此时在数组最后的数是10,为什么会是10呢?因为我们在两两比较的时候,每次都会把较大的数交换到右边,如果一个数很大的话,那么它就会被不断交换,向右移动,直到遇到一个比它大的数为止,10是数列里最大的数,所以它会一直被交换移动到最右边才停下来,也就说,我们在第一轮操作中,就把数列里最大的数移到了最右边。
  6. 接下来我们再对剩下的数进行同样的操作,还是从第一个数开始,但是因为10是已经被找出来的最大的数,我们第二轮就不需要对10再作比较了,也可以说10已经是有序的了,因为它的位置就是最后一位,因为它是整个数列中最大的数,这就等于我们第二轮操作的目标数列变成了[5, 4, 7, 9]
  7. 还是按照第一轮的步骤,第二轮我们全部交换后得到的数列是[4, 5, 7, 9]。这一轮我们找到了第二大的数9,并让它交换到了最右边。
  8. 然后进行第三轮,我们操作的数列是[4, 5, 7]
  9. 直到只剩下最后一个数的时候,我们的整个数列都是有序的了。

例 2

以数组[5, 1, 4, 2, 8]为例说明,加粗的数字表示每次循环要比较的两个数字:

  1. 第一次外循环
    ( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), 5 > 1 交换位置
    ( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), 5 > 4 交换位置
    ( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), 5 > 2 交换位置
    ( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), 5 < 8 位置不变
  2. 第二次外循环(除开最后一个元素8,对剩余的序列)
    ( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), 1 < 4 位置不变
    ( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), 4 > 2 交换位置
    ( 1 2 4 5 8 ) → ( 1 2 4 5 8 ), 4 < 5 位置不变
  3. 第三次外循环(除开已经排序好的最后两个元素,可以注意到上面的数组其实已经排序完成,但是程序本身并不知道,所以还要进行后续的循环,直到剩余的序列为 1)
    ( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
    ( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
  4. 第四次外循环(最后一次)
    ( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

代码实现

protected int[] Sort(int[] num) {
    for (int i = 0; i < num.length; i++)
        for (int j = 1; j < num.length - i; j++)
            if (num[j - 1] > num[j]) {
                /* 交换 */
                int t = num[j];
                num[j] = num[j - 1];
                num[j - 1] = t;
            }
    return num;
}

复杂度及稳定性

时间复杂度 $O(n^2)$

若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数$C$和记录移动次数$M$均达到最小值$C_{min}=n-1$,$M_{min}=0$.
所以,冒泡排序最好的时间复杂度为$O(n)$
若初始文件是逆序的,需要进行$n-1$趟排序。每趟排序要进行$n-i$次关键字的比较$(1\leq i\leq n-1)$,且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值: $C_{max}=\frac{n(n-1)}2=O(n^2)$ , $M_{max}=\frac{3n(n-1)}2=O(n^2)$
所以,冒泡排序最坏的时间复杂度为$O(n^2)$
综上所述,冒泡排序的平均时间复杂度为$O(n^2)$

空间复杂度 $O(1)$

只需要一个用于交换的辅助空间,其余的元素均在原数列中交换,所以空间复杂度为$O(1)$

稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法

优化

别以为冒泡排序就没有优化,其实冒泡排序还是有优化空间的,这里给出两种优化的方案

方案1

我们可以假设排序进行到一半的时候,数列就已经排好序了,按照冒泡排序的步骤,程序还是会继续进行下一轮的扫描比较,直到最后,显然后面的循环都是没有意义的,这个时候就可以通过设置一个flag来判断当前的这一趟循环是否存在交换,如果没有发生交换,那么说明这个时候数列已经是有序的了.

protected int[] Sort(int[] num) {
    boolean flag = true;	//是否存在交换的标志
    int lenght = num.length - 1;
    while (flag) {
        flag = false;
        for (int j = 1; j < lenght; j++)
            if (num[j - 1] > num[j]) {
                /* 交换 */
                int t = num[j];
                num[j] = num[j - 1];
                num[j - 1] = t;
                flag = true;
            }
            lenght--;
    }
    return num;
}

方案2

这次我们来缩短需要排序的数列,假设有数组在某一趟循环的开始是这样的[7, 5, 4, 8, 10, 12, 15],进行一轮扫描之后我们得到数组[5, 4, 7, 8, 10, 12, 15]可以发现从第三个元素开始到最后都已经是有序的,所以实际上需要排序的只是前面的两个元素,这就大大缩短了需要排序的数列的长度.

protected int[] Sort(int[] num) {
    int lenght, flag = num.length;
    while (flag > 0) {
        lenght = flag;
        flag = 0;
        for (int j = 1; j < lenght; j++)
            if (num[j - 1] > num[j]) {
                /*交换 */
                int t = num[j];
                num[j] = num[j - 1];
                num[j - 1] = t;
                flag = j;
            }
        }
    return num;
}

实际测试3

数据规模 原始冒泡排序 优化方案1 优化方案2
1000 6 6 6
10000 126 126 124
100000 14060 14064 14103
  1. 文中的所有说到的排序无特别说明默认按由左往右的升序. 

  2. 一个元素被放到正确的位置上我们称这个数已经有序了. 

  3. 实际测试的时间单位均为ms,数据规格均为int范围内,时间按四舍五入取整 


评论