冒泡排序

发表于:，更新于:，By Guodong
大纲
  1. 1. 一个flash让你明白冒泡排序原理
  2. 2. 算法介绍
  3. 3. 代码实现
  4. 4. 总结

写过好多次排序了，我总感觉冒泡是最难的，这次仔细阐述一下冒泡排序的原理。希望能给和我有一样问题的人一些帮助。

一个flash让你明白冒泡排序原理

http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/maopaopaixu.htm

算法介绍

假设数组为a，数组长度为n，不考虑边界条件和数组长度为1的情况。以一次冒泡为例，多次冒泡重复此过程即可。

  1. index=n-1;
  2. 如果index-1=0，本次冒泡结束，否则进入3；
  3. a[index]和a[index-1]的元素比较大小，若a[index-1]>a[index],交换a[index-1]和a[index]，index=index-1，返回2。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
public static void bubbleSort1(int[] a) {
    //i的作用，循环次数，循环“数组长度-1”次就完成排序了
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = a.length - 1; j > 0; j--) {
            if (a[j] < a[j - 1]) {
                int tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
            }
        }
    }
}

这是最基本的冒泡排序，如果你仔细换茬，你会发现这个冒泡排序和你经常写的不太一样。
第4行的内层循环中，没有使用i。这也是我在第二行添加了i的作用的原因。
这种情况下的时间复杂度和空间复杂度是这样的：
最好o(n^2)，最差o(n^2)，平均o(n^2)，空间复杂度o(1)，稳定。

为了减少内层循环次数，可以将第4行代码进行如下修改：

1
for (int j = a.length - 1; j > i; j--) {

此时，i的作用不仅是控制外层循环的次数，也控制了内存循环的次数，外层循环每完成一次，内层循环执行的次数就-1。完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void bubbleSort2(int[] a) {
    /**
     * i的作用,
     * 1. 循环次数，循环“数组长度-1”次就完成排序了
     * 2. 限制内层循环遍历的次数，外层循环每完成一次，内存循环遍历次数-1
     */
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = a.length - 1; j > i; j--) {
            if (a[j] < a[j - 1]) {
                int tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
            }
        }
    }
}

这种情况下的时间复杂度和空间复杂度是这样的：
最好o(n^2)，最差o(n^2)，平均o(n^2)，空间复杂度o(1)，稳定。

然而被人熟知的冒泡排序算法中，时间复杂度最好的是o(n)。实现的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void bubbleSort3(int[] a) {
    /**
     * i的作用,
     * 1. 循环次数，循环“数组长度-1”次就完成排序了
     * 2. 限制内层循环遍历的次数，外层循环每完成一次，内存循环遍历次数-1
     */

    boolean flag = true;//flag为true，表示已经排序完成。
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = a.length - 1; j > i; j--) {
            if (a[j] < a[j - 1]) {
                int tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
                flag = false;
            }
        }
        if (flag) {
            return;
        }
    }
}

这种情况下的时间复杂度和空间复杂度是这样的：
最好o(n)，最差o(n^2)，平均o(n^2)，空间复杂度o(1)，稳定。

总结

冒泡排序除非特定的业务场景，没有人会使用。
之所以存在这种排序算法，更多的是让人理解排序的基本概念。
上面列出的三种排序，我个人觉得都是标准的冒泡排序，也不一定说最好的时间复杂度必须是o(n)才能叫冒泡排序，只是各种实现上性能有所不同。你怎么看？