为什么左枢轴快速排序对随机数组的排序耗时远低于有序/逆序数组？

问题原因分析 #

1. 快速排序的时间复杂度差异是核心原因

• 你实现的快速排序选择左端点作为基准值，当输入数组完全有序/完全逆序时，每次分区都会把数组切分为长度为0和n-1的两部分，快排直接退化为O(n²)的时间复杂度，这就是有序、逆序数组耗时达到几秒的原因。
• 随机填充的数组完全符合快排的平均输入场景，时间复杂度为O(n log n)，和O(n²)的运算量差了上千甚至上万倍。以你测试的最大80万规模为例，O(n log n)的运算量仅在千万级别，Java处理这类运算仅需要几毫秒，所以耗时小于0.01秒是正常现象。

2. 计时精度限制
   你使用的System.currentTimeMillis()的计时精度受操作系统限制，很多系统的精度最低只有10ms，所以不足10ms的耗时会显示为小于0.01秒。如果需要更精确的耗时统计，可以替换为精度更高的System.nanoTime()，换算成秒的时候除以1e9即可，示例修改如下：

long start = System.nanoTime();
Sort.quicksort(a[k], 0, a[k].length - 1);
long end = System.nanoTime();
double time = (end - start) / 1e9;
System.out.println("Time for " + types[k] + ": " + time + " seconds.");

验证建议 #

你可以把输入规模调整到100万以上，随机数组的耗时会明显上升到几十毫秒级别，就能直观看到耗时随规模的变化了。另外你也可以把随机数组的测试顺序放到有序、逆序数组之前，排除JIT即时编译优化的干扰（当前场景下这个干扰影响很小）。

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