数据结构与算法：冒泡排序

原理

从前到后，连续相连两个数对比，如果前一个数大于后一个数，则交换。

第一次：
arr[0] 和 arr[1] 对比，若arr[0] 大于 arr[1]， 交换两个值。
arr[1] 和 arr[2]对比，若arr[1] 大于 arr[2]， 交换两个值。
arr[2] 和 arr[3]对比，若arr[2]大于 arr[3]，交换两个值。
…
arr[i] 和 arr[i +1]对比，若arr[i]大于 arr[i+1]，交换两个值。
arr[n-2]和arr[n-1]对比，若arr[n-2]大于arr[n-2]，交换两个值。

至此，arr[n-1]存储的是最大值。

第二次：
确定出 arr[n-2]的值。

第n-1次：
确定出 arr[1]的值，同时确定了arr[0]的值。

图解

复杂度

时间复杂度 O(n2)
额外空间复杂度 O(1)

代码实现

java 版本

public static void bubbleSort(int[] array) {  
    if (array == null || array.length < 2) {  
        return;  
    }  
  
    for (int i = 0; i < array.length; i ++) {  // 控制第几次循环  
        for (int j = 0; j < array.length - i - 1; j ++) {  // 控制循环的范围  第一次 是 0 到 n-1, 第二次是 0 到 n -2            if (array[j] > array[j + 1]) {  
                swap(array, j, j +1);  
            }  
        }  
    }  
}

kotlin版本

fun bubbleSort(array: IntArray) {  
    if (array.size < 2) {  
        return  
    }  
  
    for (i in array.indices.reversed()) {  // i 从 N-1 到 0        for (j in (0) until i) {  
            if (array[j] > array[j + 1]) {  // 每次把最大的冒到最后。  
                // 把最小的值换到最前边来。  
                swap(array, j, j + 1)  
            }  
        }  
    }  
}