我的随机枢轴快速排序算法运行缓慢，请问存在什么问题？

核心问题：递归范围完全写错了 #

你这代码的递归逻辑彻底错了，导致数组规模较大时直接陷入无限递归，要么长时间无响应要么触发栈溢出，所以才会出现超过30就极慢、50以上无输出的情况。

看你quickSorting方法里的递归调用：

quickSorting(array, first, last - 1);
quickSorting(array, first + 1, last);

这根本不是快速排序的分治逻辑——每次递归都在处理几乎整个数组，完全没法缩小问题规模。快速排序的核心是：分区后，枢轴元素已经处于正确位置，只需要递归排序枢轴左侧的子数组（first到pivot-1）和枢轴右侧的子数组（pivot+1到last）。

修复后的递归代码 #

把递归调用改成下面这样就正常了：

private void quickSorting(int [] array, int first, int last){
    if (first  < last){
        int pivot = partitioning(array, first, last);
        // 排序枢轴左侧的子数组
        quickSorting(array, first, pivot - 1);
        // 排序枢轴右侧的子数组
        quickSorting(array, pivot + 1, last);
    }
}

额外小提示 #

• 你的分区逻辑（随机选枢轴、交换分区）是正确的，不用修改；
• 如果想进一步优化，当子数组长度小于10时可以切换为插入排序，减少递归开销；
• 可以给Random实例加个时间种子（比如new Random(System.currentTimeMillis())），避免多次运行时随机序列重复。

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