冒泡排序 bubble
算法定义
冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
算法思路
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对
- 完成一轮后，最大的数会 "浮" 到数组的末尾
- 针对所有的元素重复以上的步骤，除了最后已经排好序的元素
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
算法复杂度
- 最好时间复杂度：O (n) - 当数组已经有序时（需要优化版本才能达到）
- 最坏时间复杂度：O (n²) - 当数组逆序时
- 平均时间复杂度：O(n²)
- 空间复杂度：O (1) - 只需要一个临时变量用于交换
- 鸡尾酒排序也是如此
优点与缺点
- 优点：
- 实现简单，易于理解
- 稳定的排序算法（相等元素的相对位置不会改变）
- 原地排序，不需要额外的存储空间
- 缺点：
- 效率低，时间复杂度为 O (n²)
- 元素移动次数多，性能较差
- 不适合大规模数据排序
应用场景
- 小规模数据的排序
- 教学场景（理解排序算法的基础原理）
- 对算法的简洁性要求高于效率时
各版本优化说明
- 基本版：最原始的实现，无论数组是否有序都会进行完整的比较
- 优化版 1：
- 添加了一个标志位判断本轮是否有交换
- 如果没有交换，说明数组已经有序，可以提前退出
- 最好情况下时间复杂度优化到 O (n)
- 优化版 2：
- 记录最后一次交换的位置，以此作为下一轮比较的边界
- 减少了不必要的比较次数
- 对于部分有序的数组效率提升明显
- 鸡尾酒排序：
- 双向冒泡，先从左到右，再从右到左
- 对于一些特殊情况（如小元素在数组末尾）效率更高
- 适合大部分元素已经有序，但个别元素位置错误的情况
通过这些优化，冒泡排序在某些场景下的性能可以得到显著提升，但总体而言，对于大规模数据排序，还是推荐使用更高效的算法如快速排序、归并排序等。
举例说明
要排序数组：int[] arr={6,3,8,2,9,1};
第一趟排序：
第一次排序：6和3比较，6大于3，交换位置： 3 6 8 2 9 1
第二次排序：6和8比较，6小于8，不交换位置：3 6 8 2 9 1
第三次排序：8和2比较，8大于2，交换位置： 3 6 2 8 9 1
第四次排序：8和9比较，8小于9，不交换位置：3 6 2 8 9 1
第五次排序：9和1比较：9大于1，交换位置： 3 6 2 8 1 9
第一趟总共进行了5次比较， 排序结果： 3 6 2 8 1 9
---------------------------------------------------------------------
第二趟排序：
第一次排序：3和6比较，3小于6，不交换位置：3 6 2 8 1 9
第二次排序：6和2比较，6大于2，交换位置： 3 2 6 8 1 9
第三次排序：6和8比较，6大于8，不交换位置：3 2 6 8 1 9
第四次排序：8和1比较，8大于1，交换位置： 3 2 6 1 8 9
第二趟总共进行了4次比较， 排序结果： 3 2 6 1 8 9
---------------------------------------------------------------------
第三趟排序：
第一次排序：3和2比较，3大于2，交换位置： 2 3 6 1 8 9
第二次排序：3和6比较，3小于6，不交换位置：2 3 6 1 8 9
第三次排序：6和1比较，6大于1，交换位置： 2 3 1 6 8 9
第二趟总共进行了3次比较， 排序结果： 2 3 1 6 8 9
---------------------------------------------------------------------
第四趟排序：
第一次排序：2和3比较，2小于3，不交换位置：2 3 1 6 8 9
第二次排序：3和1比较，3大于1，交换位置： 2 1 3 6 8 9
第二趟总共进行了2次比较， 排序结果： 2 1 3 6 8 9
---------------------------------------------------------------------
第五趟排序：
第一次排序：2和1比较，2大于1，交换位置： 1 2 3 6 8 9
第二趟总共进行了1次比较， 排序结果： 1 2 3 6 8 9
---------------------------------------------------------------------
最终结果：1 2 3 6 8 9
---------------------------------------------------------------------
由此可见：N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数
for(int i=1; i<arr.length; i++){
for(int j=1; j<arr.length-i; j++){
//交换位置
}
}
代码
import java.util.Arrays;
import java.util.Date;
/**
* 冒泡排序
* 设数组的长度为n：
* （1）比较前后相邻的二个数据，如果前面数据大于后面的数据，就将这二个数据交换。
* （2）这样对数组的第0个数据到n-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第n-1个位置。
* （3）n=n-1，如果n不为0就重复前面二步，否则排序完成。
*/
import java.util.Arrays;
public class BubbleSort {
// 1. 基本版冒泡排序
public static void bubbleSortBasic(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
// 外层循环控制需要进行多少轮比较
for (int i = 0; i < n - 1; i++) {
// 内层循环控制每轮比较的元素范围
for (int j = 0; j < n - 1 - i; j++) {
// 相邻元素比较，如果顺序错误则交换
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 2. 优化版1：添加标志位，判断是否已经有序
public static void bubbleSortOptimized1(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false; // 标志位，判断本轮是否有交换
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果本轮没有交换，说明数组已经有序，提前退出
if (!swapped) {
break;
}
}
}
// 3. 优化版2：记录最后一次交换的位置，减少比较范围
public static void bubbleSortOptimized2(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
int lastSwapIndex = 0; // 记录最后一次交换的位置
int sortBorder = n - 1; // 无序数组的边界，每次只需要比较到这里
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < sortBorder; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
lastSwapIndex = j; // 更新最后一次交换的位置
}
}
sortBorder = lastSwapIndex; // 更新无序数组的边界
if (!swapped) {
break;
}
}
}
// 4. 优化版3：鸡尾酒排序（双向冒泡排序）
public static void cocktailSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
int left = 0; // 左边界
int right = n - 1; // 右边界
while (left < right) {
// 从左到右，将最大的元素移到右边
for (int i = left; i < right; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
right--;
// 从右到左，将最小的元素移到左边
for (int i = right; i > left; i--) {
if (arr[i] < arr[i - 1]) {
int temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
}
}
left++;
}
}
public static void main(String[] args) {
int[] arr1 = {64, 34, 25, 12, 22, 11, 90};
int[] arr2 = Arrays.copyOf(arr1, arr1.length);
int[] arr3 = Arrays.copyOf(arr1, arr1.length);
int[] arr4 = Arrays.copyOf(arr1, arr1.length);
bubbleSortBasic(arr1);
System.out.println("基本版: " + Arrays.toString(arr1));
bubbleSortOptimized1(arr2);
System.out.println("优化版1: " + Arrays.toString(arr2));
bubbleSortOptimized2(arr3);
System.out.println("优化版2: " + Arrays.toString(arr3));
cocktailSort(arr4);
System.out.println("鸡尾酒排序: " + Arrays.toString(arr4));
}
}