Java Quicksort算法Stack Overflow与大数组大小

Question

我正在努力实现一个Quicksort算法，我必须在数组大小高达100,000的情况下正常工作。一旦我尝试排序大小为1,000,000，我就会出现堆栈溢出错误（由于我的算法的递归功能，这是我最好的理解）。我知道之前已经在这里提出过这个问题，但这些答案都没有帮助我。我已经仔细查看了我的代码，甚至将它从Java教科书中建模，只是为了仔细检查，仍然没有修复。我一直在这里阅读至少一个小时试图解决这个问题，我读到调用堆栈最多可以容纳8MB左右，具体取决于系统。我想知道是否：

• 我的算法错了
• 1,000,000个元素太大而无法用于快速排序（使用此编译器）。

编辑：对任何感兴趣的人：我发现将我的随机间隔从1-9增加到1-n（n是正在排序的序列的大小，例如：1-1000000），我的快速排序速度非常快，当然也没有有任何溢出问题。

我现在要和司机一起提交我的代码，希望有人可以快速告诉我出错的地方。

public class QuickSort {

public static void main(String[] args) {

    //JUST TO TEST THAT IT WORKS
    int[]A = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; //worst case

    quickSort(A, 0, A.length-1);

    //print the array
    for (int a :A)
        System.out.print(a+" ");
    System.out.println();

}

/**
 * Quicksort algorithm, O(n log n) best and average case, O(n^2) worst case
 * @param S sequence to sort
 * @param a the lower bound of sequence
 * @param b upper bound of sequence
 */
public static void quickSort(int[]S, int a, int b) {
    if (a >= b)
        return;
    int p = S[b]; //setting pivot to the last element in sequence
    int l = a;
    int r = b - 1;
    int temp;

    while (l <= r) { //once left and right have crossed this will end while
        while (l<= r && S[l] <= p) {
            l++; //move in from left side until found an element greater than the pivot
        }
        while (l <= r && S[r] >= p) {
            r--; //move in from right side until element found less than the pivot
        }
        if (l <= r) {
            //swap S[l] and S[r] //swap the left and right elements if they haven't crossed
            temp = S[l];
            S[l] = S[r];
            S[r] = temp;
            l++;
            r--;
        }
    }
    //left and right have crossed here
    //swap S[l] and S[b] //put the pivot back to the new partition spot
    temp = S[l];
    S[l] = S[b];
    S[b] = temp;
    quickSort(S, a, l-1); //call quicksort on our new sublists partitioned around our pivot
    quickSort(S, l+1, b);
    //recursive calls

}

}

司机：

import java.util.Random;

public class SortingCompare {

public static void main(String[] args) {
    Random rand = new Random();
    System.out.printf("Sorting Run Times:\n");
    System.out.printf("Array Size   Insertion Sort%5s%s\n", " ","Quick sort");

        int A[] = new int[100000];
        int n = 100000;

        for (int i = 0; i < n; i++) {
            A[i] = rand.nextInt(9) + 1; //1-9
        }
        //array is filled with random integers

        //long start = System.currentTimeMillis();
        //InsertionSortInPlace.insertionSort(A);
        //long insertionTime = System.currentTimeMillis() - start;

        //for (int i = 0; i < n; i++) {
        //    A[i] = rand.nextInt(9) + 1; //1-9
        //}

        long startQuickSort = System.currentTimeMillis();
        QuickSort.quickSort(A, 0, A.length - 1);
        long quickTime = System.currentTimeMillis() - startQuickSort;

        System.out.printf("%-5d%10dms%15s%dms\n", n, insertionTime, " ", quickTime);

}

}

Answer 1

您应该首先对两个分区中较小的一个进行排序，以最小化堆栈使用，并对小于16个元素的分区使用插入排序。

您还需要查找Quicksort算法。在每个内循环中不需要两个测试：它们完全破坏了算法的要点;并且您的实施细节与Sedgewick的规范版本不同。

Answer 2

您可以使用Java中的快速排序，该快速排序针对性能和内存使用进行了优化，因此在您的代码中替换：

quickSort(A, 0, A.length - 1);

有：

Arrays.sort(A);

要运行修改后的代码，您需要进行以下导入：

import java.util.Arrays;