Java冒泡排序性能测试数组越界与平均值计算问题求助

现有代码错误原因 #

• 数组越界报错原因
  当前版本中你使用排序逻辑内的数组遍历下标i作为耗时存储数组bubbleSortTime的索引，当排序数组长度超过500（比如你定义的10000长度大数组）时，i会超过499（长度为500的数组最大下标），触发越界报错。
  最初版本没有越界是因为你在for(x=0;x<500;x++)的循环体中额外加了一次x++，相当于每次迭代x自增2，实际只跑了250次迭代就退出循环，不会触发越界，但不符合你要求的500次迭代的需求。
• 每次循环平均值相同原因
  1. 你仅在调用bubbleSort方法前生成一次数组，第一次排序完成后数组已经是有序状态，后续迭代排序已有序的数组耗时极低，且你每次迭代都对长度为500的耗时数组全量求和，未赋值的位置默认值为0，导致平均值始终不变。
  2. 你把平均值计算逻辑写在了迭代循环内部，每跑一次迭代就计算一次平均，不符合“500次全部跑完再输出”的需求。

疑问解答 #

• 如何保证每次循环都使用未排序的新数组：将数组生成逻辑放到迭代循环内部，每次迭代都调用createArrayWithRandomInts生成全新的随机数组，不要在循环外生成数组后传入排序方法。
• 如何正确存储运行时长：使用迭代次数作为耗时数组的下标，比如第k次迭代的耗时存储到bubbleSortTime[k]，不要使用排序逻辑中的遍历下标。
• 如何对另一种规模的数组重复执行测试：将测试逻辑抽为通用方法，传入数组规模、排序实现作为参数，不同规模的数组只需调用该方法即可，无需重复编写逻辑。

修复后完整代码 #

import java.util.function.Consumer;

public class SortBenchmark {
    public static void main(String[] args) {
        // 测试小规模数组：长度99，跑500次
        runSortBenchmark("冒泡排序", 99, 500, SortBenchmark::bubbleSort);
        // 测试大规模数组：长度10000，跑500次
        runSortBenchmark("冒泡排序", 10000, 500, SortBenchmark::bubbleSort);
    }

    /**
     * 通用排序性能测试方法
     * @param sortName 排序方法名称
     * @param arraySize 测试数组规模
     * @param iterations 迭代次数
     * @param sortFunction 排序实现
     */
    private static void runSortBenchmark(String sortName, int arraySize, int iterations, Consumer<int[]> sortFunction) {
        long[] sortTime = new long[iterations];
        for (int i = 0; i < iterations; i++) {
            // 每次迭代生成全新的随机数组
            int[] array = createArrayWithRandomInts(arraySize);
            long start = System.nanoTime();
            sortFunction.accept(array);
            long end = System.nanoTime();
            // 用迭代次数作为下标存储耗时
            sortTime[i] = end - start;
        }
        // 所有迭代跑完再计算平均
        long sum = 0;
        for (long time : sortTime) {
            sum += time;
        }
        double average = (double) sum / iterations;
        System.out.printf("%s 长度为%d的数组 平均耗时：%.2f 纳秒%n", sortName, arraySize, average);
    }

    /**
     * 冒泡排序实现（仅保留排序逻辑）
     * @param array 待排序数组
     */
    static void bubbleSort(int[] array) {
        int temp;
        for (int i = 0; i < array.length; i++) {
            boolean alreadySorted = true;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    alreadySorted = false;
                    temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
            if (alreadySorted) {
                break;
            }
        }
    }

    static int[] createArrayWithRandomInts(int size) {
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = (int) (Math.random() * Math.random() * 100000);
        }
        return array;
    }
}

内容的提问来源于stack exchange，提问作者Zachary Mull