Java排序算法基准测试平均运行时间异常升高问题求助

核心问题原因 #

• 排序逻辑存在语法错误：merge函数中else if (array2Index < array1Index) ;末尾多了一个多余的分号，导致后续的数组拷贝逻辑不受条件控制，每次合并都会错误写入数据，最终数组元素被打乱甚至出现异常值，越往后排序耗时越高。
• 输入数组未重置：初始仅生成一次随机数组，第一个排序算法执行完成后数组已经变为有序状态，后续所有算法、以及同一个算法的多次循环测试，都是对已经有序（或被merge错误打乱）的数组执行排序，输入状态完全不一致，测试结果没有参考价值。
• 循环变量重复自增：每个排序测试函数的外层循环for (x = 0; x< 500; x++)已经会自动对x自增，但是循环体内部又额外加了x++，导致循环实际仅执行250次，且x最终会超出时间统计数组的索引范围，触发数组越界异常。
• 时间类型强制转换错误：System.nanoTime()返回的是long类型的纳秒值，大数组排序耗时很容易超过int的最大值（约21亿纳秒=2.1秒），强制转int会导致数值溢出变成负数，累加计算平均值时完全错误。
• 缺少JIT预热：Java虚拟机会对高频执行的代码做JIT即时编译，刚启动时的解释执行速度远低于编译后的本地代码，未预热直接统计时间会导致前几次测试结果偏差极大。

修复建议 #

1. 删除merge函数中else if (array2Index < array1Index)末尾的多余分号，修正合并逻辑。
2. 每个排序算法测试前、以及同一个算法每次循环测试前，都深拷贝一份初始生成的随机数组作为输入，保证所有测试的输入状态完全一致，避免前一次排序修改输入数组。
3. 删除所有排序测试函数循环体内部的x++语句，避免循环变量重复自增。
4. 时间统计数组改为long类型，不要做int强制转换，避免数值溢出。
5. 正式统计耗时前，先将每个排序算法执行10~20次做预热，等JIT编译完成后再正式统计数据。
6. 调整大数组的测试次数：O(n²)复杂度的排序算法处理50万元素的单次耗时已经很高，不需要跑500次，调整为5~10次即可，小数组测试次数可以保留500次。

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