递归实现冒泡排序的原理与实践

import java.util.Arrays;

public class RecursiveBubbleSort {

    /**
     * 递归实现冒泡排序（参数递减）
     * 每次递归将当前未排序部分的最大元素“冒泡”到末尾
     *
     * @param arr 待排序数组
     * @param n   当前需要排序的元素数量（从数组开头算起）
     */
    public static void sortingRecursionDecreasing(int[] arr, int n) {
        // 基本情况：如果只剩一个元素或没有元素需要排序，则返回
        // 当 n 为 1 时，循环条件 i < n-1 (即 i < 0) 不满足，直接返回
        if (n <= 1) {
            return;
        }

        // 执行一轮冒泡，将当前最大的元素移动到 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("原始数组 (递减参数): " + Arrays.toString(array1));
        sortingRecursionDecreasing(array1, array1.length);
        System.out.println("排序后数组 (递减参数): " + Arrays.toString(array1));
    }
}

import java.util.Arrays;

public class RecursiveBubbleSort {

    /**
     * 递归实现冒泡排序（参数递增）
     * n 记录已经有多少个元素从数组末尾开始排好序
     *
     * @param arr 待排序数组
     * @param n   已排序元素的数量（从数组末尾开始计数）
     */
    public static void bubbleRecursionIncreasing(int arr[], int n) {
        // 基本情况：如果 n 等于数组长度，表示所有元素都已排序
        // 注意：当 n 等于 arr.length - 1 时，最后一个元素已就位，可以提前返回
        if (n == arr.length) {
            return;
        }

        // 执行一轮冒泡，将当前未排序部分的最大元素移动到 arr.length - 1 - n 的位置
        // 循环范围：i 从 0 到 arr.length - 1 - n - 1
        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("原始数组 (递增参数): " + Arrays.toString(array2));
        bubbleRecursionIncreasing(array2, 0); // 初始时，0个元素已排序
        System.out.println("排序后数组 (递增参数): " + Arrays.toString(array2));
    }
}

// 优化后的基本情况
public static void bubbleRecursionIncreasingOptimized(int arr[], int n) {
    if (n == arr.length - 1) { // 当倒数第二个元素就位时，最后一个元素也已就位
        return;
    }
    // ... 其他代码不变 ...
    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;
        }
    }
    bubbleRecursionIncreasingOptimized(arr, n + 1);
}