使用大尺寸（100000）数组执行快速排序时出现Java StackOverflower错误

Question

在系统中处理衡量快速排序效率的作业。纳米时代。我的代码适用于其他数组大小（例如100；1000；10000），但是，当我尝试使用大小为100000的数组的方法时，我收到一个StackOverflower错误。还值得注意的是，对于InsertionSort和BubbleSort，我使用了大小为100000的数组

我们的目标是运行QuickSort 105次，测量前5次之后的100次，使用数组以纳米时间测量运行时间

首先，我创建一个预定大小的随机整数数组。接下来，我将克隆该int数组并将克隆传递给所需的排序方法（本例中为快速排序）。最后，我创建了一个方法，使用QuickSort运行所需的次数。方法如下：

public static void quickSort(int[] unsortedArray, int size, int max) {
    long averageTime = 0;

    for (int i = 0; i < RUN_TIMES; i++) {
        if (i < 5) {
            QuickSort.quickSort(unsortedArray);
        } else {
            long startTime = System.nanoTime();
            QuickSort.quickSort(unsortedArray);
            long stopTime = System.nanoTime();
            long runTime = stopTime - startTime;
            averageTime = averageTime + runTime;
        }
    }

    System.out.println("Quicksort time for size " + size +
            " and max " + max + ": " + averageTime / DIVISOR);
}

运行时间设置为105，除数设置为100。讲师提供的快速排序代码如下所示：

public static void quickSort(int[] list) {
quickSort(list, 0, list.length - 1);
  }

 private static void quickSort(int[] list, int first, int last) {
if (last > first) {
  int pivotIndex = partition(list, first, last);
  quickSort(list, first, pivotIndex - 1);
  quickSort(list, pivotIndex + 1, last);
}
  }

  private static int partition(int[] list, int first, int last) {
int pivot = list[first]; // Choose the first element as the pivot
int low = first + 1; // Index for forward search
int high = last; // Index for backward search

while (high > low) {
  // Search forward from left
  while (low <= high && list[low] <= pivot)
    low++;

  // Search backward from right
  while (low <= high && list[high] > pivot)
    high--;

  // Swap two elements in the list
  if (high > low) {
    int temp = list[high];
    list[high] = list[low];
    list[low] = temp;
  }
}

while (high > first && list[high] >= pivot)
  high--;

// Swap pivot with list[high]
if (pivot > list[high]) {
  list[first] = list[high];
  list[high] = pivot;
  return high;
}
else {
  return first;
}

我做错了什么？最后一个想法是，我正在更新的MacBookPro上使用NetBeans。只是想确定我分享了一切。任何帮助都将不胜感激

更新：这是我用来生成数组的代码：

private static int[] createArray(int size, int maxValue) {
    int arraySize = size;
    /*
        Create array of variable size
        Random int 1 - 999
    */
    // Constructor for random and variable declaration
    Random random = new Random();
    int x;

    // Constructor for ArrayList<Integer>
    ArrayList<Integer> tempArrayList = new ArrayList<>();

    // While loop used to create ArrayList w/100 unique values
    while (tempArrayList.size() < arraySize) {
        // Creates int value between 1 and 999
        x = random.nextInt(maxValue) + 1;

        // Checks if generated value already exists within ArrayList
        if(!tempArrayList.contains(x)) {
            // Add to ArrayList
            //System.out.println("Added: " + x);

            tempArrayList.add(x);
        } else {
            // Do nothing
        } // end if - else
    } // end while loop

    // Convert ArrayList<Integer> to int[]
    int[] arrayList = tempArrayList.stream().mapToInt(i -> i).toArray();

    return arrayList;
} // end createArray method

Answer 1

简短版本：您的列表已排序，QS需要对已排序的列表进行大量递归

快速排序是一种递归算法，最坏情况下的时间复杂度为O(n)，在对列表排序时，对于您的轴心选择（第一项），可以实现该算法

在第一次迭代之后，它是这样的，因为快速排序已经就位，即它修改了输入数组

在第一次迭代之后，该数组上的快速排序需要n递归或100000。太多了。考虑一个更好的排序算法，或者一个不使用递归的算法，或者考虑没有递归地重写它。

Answer 2

您已经编写了一个递归算法，它对堆栈施加了很大的压力，然后给它一个大数据集，给定堆栈压力与问题大小的平方成正比，这就不存在堆栈溢出的原因。将算法重新编码为循环，不要在堆栈上留下太多垃圾