因此，如果元素已经排序，并且总是选择最后一个元素作为主元，这意味着每次递归和划分元素时，数组中的所有元素都绝对小于主元，并且没有元素大于主元，这将导致不平衡的划分，因此低分区quickSort(arr, start, pivot - 1);的代码行将不得不进行比正常情况多得多的递归调用，从而导致堆栈溢出。这是快速排序中的最坏情况（O（n^2））。
为了解决这个问题，我让算法选择随机的主元，而不是总是选择最后一个元素作为主元，如下所示：

private static int partition(String[] arr, int start, int end) {
        int randomIndex = new Random().nextInt(end - start + 1) + start; // random pivot to avoid worst case scenario more often during recursion (when array is already sorted)
        String pivot = arr[randomIndex];
        int i = start - 1;

        String temp = arr[randomIndex];
        arr[randomIndex] = arr[end];
        arr[end] = temp;

        for (int j = start; j < end; ++j)
        {
            if (arr[j].compareTo(pivot) < 0)
            {
                ++i;
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        ++i;
        temp = arr[i];
        arr[i] = pivot;
        arr[end] = temp;

        return i;
    }

更多说明：

• 为什么是nextInt(end - start + 1) + start;？

我们需要在数组的特定分区中的随机索引处选择元素，这个参数将生成一个介于0到分区的最后一个索引end - start之间的数字（不包含）。要包含最后一个索引作为可能的透视。我们必须添加一个。然后我们将最小的索引添加到结果中，因为我们不希望包含低分区的索引。当方法进行高分区时，最低索引不会是0，而是一个更大的数字，当我们将最低索引添加到结果中时，我们将所有小于该数字的数字排除在可能的透视表之外。

• 为什么在进入for循环之前要进行交换？

因为我们仍然遵循着和以前一样的逻辑;即每次我们发现一个大于主元的元素时递增i，而不从上一个索引移动主元，也不意外地改变它，然后，在最后，我们交换最后一个元素，其中主元安全地保持与比主元最小的最后一个元素的后续索引的任何交换。
要执行前面的操作，我们必须确保pivot元素确实在交换之前的最后一个索引中，这就是为什么在进入for循环之前，我们要进行交换。

堆栈溢出可以通过只在较小的分区上使用递归，并在较大的分区上循环返回来防止，堆栈空间复杂度为O（log2（n）），但最坏情况下的时间复杂度仍然为O（n^2），并且600000个元素可能花费太长时间：

private static void quickSort(String[] arr, int start, int end) {
    while(end > start){
        int pivot = partition(arr, start, end);
        if((pivot - start) <= (end - pivot)){
            quickSort(arr, start, pivot - 1);
            start = pivot+1;
        } else {
            quickSort(arr, pivot + 1, end);
            end = pivot-1;
        }
    }
}

一个更好的选择是使用中间值、中值3或随机枢轴，如Sheep_步行者的答案所示。