数据结构（八）：冒泡排序

• 冒泡排序是一种交换排序，通过比较相邻的元素，如果反顺序则交换，直到没有反序的元素为止

冒泡排序代码

int[] arr = new int[]{1, 3, 6, 4, 7, 8, 5, 10, 9};
// API 实现
Arrays.sort(arr);
// 冒泡排序
int temp;
for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length - i - 1; j++) {
    if(arr[j]>arr[j+1]){
        temp = arr[j];
        arr[j]=arr[j+1];
        arr[j+1]=temp;
        }
    }
}

• 优化：添加一个 flag 来判断当前循环是否已经有序，如果有序则退出循环

boolean flag = true;
int[] arr = new int[]{1, 3, 6, 4, 7, 8, 5, 10, 9};
// 冒泡排序
int temp;
for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length - i - 1; j++) {
        if(arr[j]>arr[j+1]){
            temp = arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=temp;
            flag = false;
        }
    }
    if (!flag){
        break;  // 退出循环
    }
}

冒泡排序性能

• 最好的情况就是排序的表本身就是有序的，那么我们只要比较次数，时间复杂度为 O(n)，最坏的情况是排序表是逆序的的，时间复杂度为 O(n²)