QuickSort 实现不适用于大输入

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);

QuickSort 实现不适用于大输入

QuickSort implementation not working for large input

quicksort