递归实现冒泡排序：两种策略与核心原理深度解析

import java.util.Arrays;

public class RecursiveBubbleSort {

    /**
     * 传统递归冒泡排序方法，通过递减参数n控制排序范围。
     * 每一趟将当前子数组的最大元素“冒泡”到末尾。
     * @param arr 待排序数组
     * @param n 当前需要排序的子数组长度
     */
    public static void sortingRecursionDecreasing(int[] arr, int n) {
        // 递归基：当子数组长度为1时，说明只剩一个元素，无需排序，直接返回。
        if (n == 1) {
            return;
        }

        // 执行一趟冒泡排序，将当前子数组（长度为n）的最大元素移到 arr[n-1]
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                // 交换元素
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }

        // 递归调用：对剩余的 n-1 个元素进行排序
        sortingRecursionDecreasing(arr, n - 1);
    }

    public static void main(String[] args) {
        int[] array1 = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("原始数组1: " + Arrays.toString(array1));
        sortingRecursionDecreasing(array1, array1.length); // 初始调用，对整个数组排序
        System.out.println("排序后数组1 (递减参数): " + Arrays.toString(array1));
    }
}

import java.util.Arrays;

public class RecursiveBubbleSort {

    /**
     * 另一种递归冒泡排序方法，通过递增参数n控制排序范围。
     * n表示已经有多少个元素被排序并固定在数组末尾。
     * @param arr 待排序数组
     * @param n 已经排序的元素数量（从数组末尾开始计数）
     */
    public static void bubbleRecursionIncreasing(int[] arr, int n) {
        // 递归基：当 n 等于数组长度时，表示所有元素都已排序，递归终止。
        // 或者，当 n 等于 arr.length - 1 时，意味着只剩一个元素未排序，它自然是有序的。
        // 当前实现中 n == arr.length 是一个稍微宽松的基准，意味着最后一次循环可能不执行任何操作。
        if (n == arr.length) {
            return;
        }

        // 执行一趟冒泡排序，将当前未排序部分（从 arr[0] 到 arr[arr.length-1-n]）的最大元素移到 arr[arr.length-1-n]
        // 注意循环条件：arr.length - 1 - n 会随着 n 的增加而减小，从而缩小每次冒泡的范围。
        for (int i = 0; i < arr.length - 1 - n; i++) {
            if (arr[i] > arr[i + 1]) {
                // 交换元素
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }

        // 递归调用：增加 n，表示又有一个元素被排序到正确位置
        bubbleRecursionIncreasing(arr, n + 1);
    }

    public static void main(String[] args) {
        int[] array2 = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("原始数组2: " + Arrays.toString(array2));
        bubbleRecursionIncreasing(array2, 0); // 初始时，0个元素已排序
        System.out.println("排序后数组2 (递增参数): " + Arrays.toString(array2));
    }
}