编程►算法

《啊哈！算法》学习笔记之冒泡排序

基本思想

冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。

以从大到小为例。

每次都是比较相邻的两个数，如果后面的数比前面的数大，则交换这两个数的位置。一直比较下去直到最后两个数比较完毕后，最小的数就在最后一个了。就如同是一个气泡，一步一步往后“翻滚” ，直到最后一位。所以这个排序的方法有一个很好听的名字“冒泡排序” 。

每将一个数归位我们将其称为“一趟” 。每一趟，都是将小的归位（先是最小，后次小，次后第三小…）。

如果有 n 个数进行排序，只需将 n-1 个数归位，也就是说要进行n-1 趟操作。而“每一趟”都需要从第 1 位开始进行相邻两个数的比较，将较小的一个数放在后面，比较完毕后向后挪一位继续比较下面两个相邻数的大小，重复此步骤，直到最后一个尚未归位的数， 已经归位的数则无需再进行比较 （已经归位的数你还比较个啥， 浪费表情） 。

核心思想

冒泡排序的核心部分是双重嵌套循环。

时间复杂度：O（N^2）

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static void main(String[] args) {
    int length = 10;
    int maxValue = 20;
    int[] array = new int[length];
    Random r = new Random();
    for (int i = 0; i < array.length; i++) {
        array[i] = r.nextInt(maxValue);
    }
    System.out.println("before");
    print(array);
    bubbleSort(array);
    System.out.println("after");
    print(array);
}
 
 
public static void bubbleSort(int[] array) {
    int tmp = 0;
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length-1; j++) {
            if (array[j] < array[j+1]) {//如果前一个比后一个小，则进行交换。这样子就可以是从大到小。
                tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
            }
        }
    }
}
 
 
public static void print(int[] array) {
    System.out.println(Arrays.toString(array));
}

总结

冒泡比较耗时