算法: 冒泡排序

冒泡排序是一种简单的排序算法，通过相邻元素的比较和交换，使较大的元素逐渐"浮"到数组末尾。

时间复杂度:最佳 O(n) | 平均 O(n²) | 最差 O(n²)

空间复杂度:O(1)

稳定性:稳定

应用场景/前提条件

• 适用于小规模数据
• 对几乎已排序的数据效率较高

算法步骤

1. 比较相邻的元素。如果第一个比第二个大，就交换它们
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对
3. 这步做完后，最后的元素会是最大的数
4. 针对所有的元素重复以上的步骤，除了已经是最大数的最后一个
5. 持续每次对越来越少(每次重复都会少一个最大数)的元素重复上面的步骤，直到没有任何一对数字需要比较

public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            // 每次遍历后，最大的i+1个元素已经排好序
            for (int j = 0; j < n - i - 1; j++) {
                // 如果当前元素大于下一个元素，则交换
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

1. 外层循环：控制排序的轮数。对于长度为 n 的数组，需要进行 n-1 轮排序。每一轮排序都会将当前未排序部分的最大元素 "冒泡" 到右侧。
2. 内层循环：负责比较相邻元素并在必要时交换它们。每一轮排序后，最大的元素已经就位，因此内层循环的次数可以逐轮减少（通过n - i - 1实现）。

   1. 每轮排序后的有序元素
   冒泡排序的特点是：每一轮结束后，最大的 i+1 个元素都会被排到数组的右侧（升序排序）。例如：
   
   第 1 轮后，最大的元素被排到了最后一个位置。
   第 2 轮后，第二大的元素被排到了倒数第二个位置。
   依此类推，第 i 轮后，最大的 i+1 个元素都已经在正确的位置上。
   
   2. 内层循环的边界
   由于右侧的 i+1 个元素已经有序，下一轮比较时就不需要再考虑它们。因此，
   每一轮需要比较的元素数量是逐渐减少的：
   
   第 1 轮需要比较 n-1 次（所有元素都参与比较）。
   第 2 轮需要比较 n-2 次（最后一个元素已经有序，不需要再比较）。
   第 i 轮需要比较 n - i - 1 次。
   
   3. 为什么是 n - i - 1？
   
   n 是数组的总长度。
   i 是当前外层循环的轮数（从 0 开始计数）。
   n - i 表示剩余未排序元素的数量。
   由于每次比较的是相邻的两个元素，因此需要进行 n - i - 1 次比较。

3. 元素交换：当发现相邻元素顺序错误时（前一个元素大于后一个元素），通过临时变量temp交换它们的位置。

 if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }

优缺点

优点

• 代码简单，容易实现
• 适合小规模数据排序
• 对于几乎已经排好序的数据，效率较高
• 稳定的排序算法

缺点

• 时间复杂度高，为O(n²)
• 随着元素数量增加，效率急剧下降
• 每次只能将一个元素移动到其最终位置，效率不高

鸡尾酒排序（双向冒泡排序）

鸡尾酒排序是冒泡排序的一种变体，它从低到高然后从高到低来回排序，比冒泡排序的效率稍微高一点：

public static void cocktailSort(int[] arr) {
    boolean swapped = true;
    int start = 0;                  // 左侧已排序边界
    int end = arr.length - 1;       // 右侧已排序边界
    
    while (swapped) {
        // 从左到右扫描，将最大元素移到右侧
        swapped = false;
        for (int i = start; i < end; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
                swapped = true;
            }
        }
        // 扫描结束后，最大元素已在end位置，因此下次扫描到end-1即可
        end--;
        
        // 如果没有交换，说明数组已排序
        if (!swapped) break;
        
        // 从右到左扫描，将最小元素移到左侧
        swapped = false;
        for (int i = end - 1; i >= start; i--) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
                swapped = true;
            }
        }
        // 扫描结束后，最小元素已在start位置，因此下次从start+1开始
        start++;
    }
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

测验

1. 冒泡排序的平均时间复杂度是多少？
2. 冒泡排序是稳定的排序算法吗？
3. 对于已经排好序的数组，优化版冒泡排序的时间复杂度是多少？
4. 冒泡排序每一轮遍历后，数组尾部会有什么特点？
5. 如何优化冒泡排序以提高效率？

测验答案

1. 冒泡排序的平均时间复杂度是O(n²)。
2. 是的，冒泡排序是稳定的排序算法。因为只有当前一个元素大于后一个元素时才交换，相等元素不会改变相对位置。
3. 对于已经排好序的数组，优化版冒泡排序的时间复杂度是O(n)。因为第一轮遍历不会发生交换，优化版会检测到这点并提前终止。
4. 冒泡排序每一轮遍历后，数组尾部会有一个元素到达其最终位置，且是当前未排序部分中的最大元素。第i轮结束后，末尾i个元素已排好序。
5. 优化冒泡排序的方法:
   • 添加标志位跟踪是否发生交换，无交换则提前终止
   • 记录最后一次交换位置，下一轮只遍历到该位置
   • 使用双向冒泡(鸡尾酒排序)，同时将最大值上浮和最小值下沉