冒泡排序笔记

核心思想

通过相邻元素的比较和交换，使较大的元素逐渐“浮”到数组的末尾（像气泡从水底冒到水面一样）

基础冒泡排序

public class BubbleSort{public static void bubbleSort(int[] arr){for(int i = 0; i  < arr.length - 1; i++){//冒泡的次数,总数-1for(int j = 0; j < arr.length - 1 - i; j++){//比较相邻的数if(arr[j] > arr[j+1]){swap(arr, j, j+1);}}}}public static void swap(int[] arr, int a, int b){int temp = arr[a];int[a] = int[b];int[b] = temp;}
}

时间复杂度：

• 最坏情况（完全逆序）：O(n²)
• 最好情况（已有序）：O(n²)（即使有序，仍然会完整遍历）

空间复杂度：O(1)

稳定性：稳定

优化版冒泡排序

优化思路

所谓优化，就是数据已经排好序的情况下提前终止冒泡排序。

判断的依据就是，当某一轮的尝试“冒泡”的过程中，如果发现数据并没有进行交换，那么这时候就直接结束排序过程。

优化代码

public class OptimizedBubbleSort{public static optimizeBubbleSort(int[] arr){int n = arr.length;boolean swapped ;for(int i = 0; i < n -1; i++){swapped = false;for(int j = 0; j < n - 1- i; j++){if(arr[j] > arr[j+1]){swapped = true;swap(arr, j , j+1);}}if(!swapped) return;}}public static void swap(int[] arr, int a, int b){int temp = arr[a];int[a] = int[b];int[b] = temp;}
}

时间复杂度：

• 最坏情况（完全逆序）：O(n²)
• 最好情况（已有序）：O(n)（即使有序，仍然会完整遍历）