冒泡法

冒泡法可以用来找队列中的最大值，也可以通过多次冒泡对集合进行排序。

核心思想

遍历数组或集合中，用当前位置的值与后面一个值相比较并且交换，使极值永远处于数组或集合的最末。

冒泡法

冒泡找最大值

逐个比对，通过交换使极值拍到末尾，但并不保证前面的顺序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

private static int max(int[] original) {
    // copy数组，不会影响原数组
    int[] newArray = Arrays.copyOf(original, original.length);

    int num1, num2;
    // 注意这里减1以提高效率
    for (int i = 0; i < newArray.length - 1; i++) {
        num1 = newArray[i];
        num2 = newArray[i + 1];
        if (num1 > num2) {
            newArray[i] = num2;
            newArray[i + 1] = num1;
        }
    }
    // 返回末端
    return newArray[newArray.length - 1];
}

为何循环中减1呢？因为不断的遍历和比较，当遍历到倒数第二个值的时候，会与倒数第一去比较，不论结果如何，最大值已经到达末尾了，所以就没有必要再去遍历到最后一个值了。

时间复杂度：O(n) 空间复杂度：O(n)

冒泡排序

在冒泡找极值的基础上加入循环，使数组或集合从后往前数依次是：极值、次极值、次次极值…

 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

private static int[] sort(int[] original, int k) {

    int[] newArray = Arrays.copyOf(original, original.length);

    int num1, num2;

    int i = 0;

    // 外层循环控制冒泡的轮数
    for (; i < k - 1; i++) {

        //记录内层是否发生过交换
        boolean flag = false;
        //内层循环控制冒泡的次数
        for (int j = 0; j < newArray.length - 1 - i; j++) {
            num1 = newArray[j];
            num2 = newArray[j + 1];
            if (num1 < num2) {
                newArray[j] = num2;
                newArray[j + 1] = num1;
                flag = false;
            }
        }

        // 如果内层一轮遍历下来美誉发生过交换，说明已经排序好了，直接跳出外层循环
        if (flag) {
            break;
        }
    }
    return newArray;
}