冒泡排序

Author Avatar
Brian Lee 8月 03, 2018
  • 在其它设备中阅读本文章

算法笔记:冒泡排序


原理

  1. 比较相邻的元素,如果第一个比第二个大,交换这两个元素
  2. 对每一对相邻元素进行同样的工作,从开始第一对到结尾最后一对。这步做完后,最后的元素会是最大的数
  3. 重复以上步骤,除了已选出的元素,直到没有任何一对元素需要比较,则序列有序

复杂度

时间复杂度

$O(n^2)$

空间复杂度

$O(1)$


图示

冒泡排序


代码

实现一

最优情况$O(n^2)$

public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            for (int j = 1; j < N - i; j++) {
                if (less(a[j], a[j - 1]))
                    exch(a, j, j - 1);
            }
        }
    }

实现二

最优情况$O(n)$

优化点 :由于冒泡排序要遍历整个未排好的部分,如果在整个排序过程中没有交换,我们就可断定列表已经排好。因此可以改良冒泡排序,使其在已知列表排好的情况下提前结束。

public static void sort2(Comparable[] a) {
        int N = a.length;
        boolean isExch = true;
        for (int i = 0; i < N && isExch; i++) {
            isExch = false;
            for (int j = 1; j < N - i; j++) {
                if (less(a[j], a[j - 1])) {
                    exch(a, j, j - 1);
                    isExch = true;
                }
            }
        }
    }

实现三

最优情况$O(n)$

优化点 :记录已排好序的位置,之后的遍历到此位置就可以停止。

public static void sort3(Comparable[] a) {
        int N = a.length;
        boolean isExch = true;
        int tail = N, temp = N;
        for (int i = 0; i < N && isExch; i++) {
            isExch = false;
            for (int j = 1; j < tail; j++) {
                if (less(a[j], a[j - 1])) {
                    exch(a, j, j - 1);
                    isExch = true;
                    temp = j;
                }
            }
            tail = temp;
        }
    }

特点

  • 每进行一趟排序,就会少比较一次,因为每进行一趟排序都会找出一个较大值

源码

https://github.com/XutongLi/Algorithm-Learn/blob/master/src/S2_Sorting/Others_Bubble_Sort/Bubble.java


本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
本文链接:http://brianleelxt.top/2018/08/03/Bubble/