快速排序实现不适用于大输入

Question

谁能告诉我为什么我的quickSortHelper函数不解决大输入?

import java.util.*;
class Program {
public static int[] quickSort(int[] array) {
// Write your code here.
quickSortHelper(array, 0, array.length - 1);
return array;
}
public static void quickSortHelper(int[] array, int l, int r){
if(l >= r){
return;
}
int pivot = l;
int leftIndex = l + 1;
int rightIndex = r;
while(rightIndex >= leftIndex ){
if(array[leftIndex] > array[pivot] && array[rightIndex] < array[pivot]){
swap(leftIndex, rightIndex, array);
}
if(array[leftIndex] <= array[pivot]){
leftIndex += 1;
}
if(array[rightIndex] >= array[pivot]){
rightIndex -= 1;
}
}
swap(pivot, rightIndex, array);
boolean leftSubarrayIsSmaller = rightIndex - 1 - l < r - (rightIndex + 1);
if(leftSubarrayIsSmaller){
quickSortHelper(array, rightIndex + 1, l);
quickSortHelper(array, l, rightIndex - 1);
}else{
quickSortHelper(array, l, rightIndex - 1);
quickSortHelper(array, rightIndex + 1, l);
}
}
public static void swap(int i, int j, int[] array){
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}

这是我的测试用例，我想如果我解决这个问题，它将是一个有效的实现。

int[] array7 = {-4, 5, 10, 8, -10, -6, -4, -2, -5, 3, 5, -4, -5, -1, 1, 6, -7, -6, -7, 8};

当前结果如下

[-10, -7, -6, -7, -6, -5, -4, -5, -4, 3, 5, -4, -2, -1, 1, 6, 8, 10, 5, 8]

可以看到，仍然没有完全排序。对于小于10个数字的小输入，

任何帮助将非常感激!

欢呼,

Answer 1

您有如下两行，它们不做任何事情:

quickSortHelper(array, rightIndex + 1, l);

将l替换为r:

quickSortHelper(array, rightIndex + 1, r);