Java冒泡排序不同规模数组的交换与比较次数统计需求

我看你已经开始着手实现冒泡排序并统计交换和比较次数了，不过有几个关键细节可以优化，同时帮你把代码补全，让它能输出1000、10000、100000元素数组下的统计数据。

原代码的问题点 #

你的内层循环边界j < arrayToSort.length-1没有考虑冒泡排序的特性：每完成一轮外层循环，数组末尾的i个元素已经是有序的，不需要再比较。这会导致大量不必要的比较，统计结果也会比实际需要的多。另外交换逻辑也没写完，需要补全赋值语句。

完整实现代码 #

import java.util.Random;

public class BubbleSortStats {

    // 冒泡排序，返回包含[比较次数, 交换次数]的数组
    public static int[] bubbleSort(int[] arrayToSort) {
        int comps = 0;
        int swaps = 0;
        int n = arrayToSort.length;
        
        for (int i = 0; i < n - 1; i++) {
            // 优化：内层循环只需要遍历到未排序的部分
            for (int j = 0; j < n - 1 - i; j++) {
                comps++; // 每次进入循环都进行了一次比较
                if (arrayToSort[j] > arrayToSort[j + 1]) {
                    swaps++; // 发生交换时计数
                    // 执行交换操作
                    int temp = arrayToSort[j];
                    arrayToSort[j] = arrayToSort[j + 1];
                    arrayToSort[j + 1] = temp;
                }
            }
        }
        return new int[]{comps, swaps};
    }

    // 生成指定大小的随机整数数组
    public static int[] generateRandomArray(int size) {
        Random random = new Random();
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(100000); // 生成0到99999的随机整数
        }
        return array;
    }

    public static void main(String[] args) {
        // 测试的三种数组规模
        int[] sizes = {1000, 10000, 100000};
        
        for (int size : sizes) {
            System.out.println("===== 数组规模：" + size + " =====");
            int[] testArray = generateRandomArray(size);
            // 注意：因为排序会修改原数组，如果需要保留原数组可以先复制一份
            int[] stats = bubbleSort(testArray);
            System.out.println("比较次数：" + stats[0]);
            System.out.println("交换次数：" + stats[1]);
            System.out.println();
        }
    }
}

代码说明 #

• 内层循环优化：j < n - 1 - i确保每轮只比较未排序的前n-1-i个元素，避免重复比较已排序的末尾元素。
• 统计逻辑：comps在每次内层循环迭代时递增（因为每次循环都会执行一次arrayToSort[j] > arrayToSort[j+1]的比较），swaps仅在实际发生元素交换时递增。
• 随机数组生成：用Random类生成随机数组，保证测试数据的随机性，统计结果更符合实际场景。
• 结果返回：用数组返回比较和交换次数，方便在主函数中统一输出不同规模的统计数据。

额外提示 #

如果需要测试最坏情况（数组完全逆序），可以把generateRandomArray改成生成逆序数组的方法，这样统计的交换和比较次数会达到最大值；如果测试最好情况（数组已排序），可以生成有序数组，此时交换次数为0，比较次数为n-1（如果没有提前终止优化的话）。

内容的提问来源于stack exchange，提问作者R.Spieth