Java 大数组大小的快速排序算法堆栈溢出

Question

我正在努力实现一个快速排序算法，我必须能够很好地处理最大 100,000 的数组。一旦我尝试以 1,000,000 的大小进行排序，我就会得到一个堆栈溢出错误（由于我的算法的递归功能，这是我最好的理解）。我知道之前有人在这里问过这个问题，但是 none 这些答案对我有帮助。我已经广泛查看了我的代码，甚至根据 Java 教科书对其进行了建模，只是为了仔细检查，但仍然没有修复。我在这里阅读了至少一个小时试图解决这个问题，并且我读到调用堆栈最多可以容纳 8MB 左右，具体取决于系统。我想知道是否：

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

编辑：致所有感兴趣的人：我发现将运行dom 间隔从 1-9 增加到 1-n（n 是排序序列的大小，例如：1 -1000000)，我的快速排序运行非常快，当然也没有任何溢出问题。

我现在要提交我的代码，driver，希望有人能迅速告诉我哪里出错了。

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

}

}

Driver:

import java.util.Random;

public class 排序比较 {

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 个元素的分区使用插入排序。

您还需要查找快速排序算法。您不需要在每个内部循环中进行两次测试：它们完全破坏了算法的要点；并且您的实施细节与 Sedgewick 的规范版本不同。

Answer 2

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

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

与：

Arrays.sort(A);

为了运行修改后的代码，您需要导入以下内容：

import java.util.Arrays;

Java 大数组大小的快速排序算法堆栈溢出

Java Quicksort algorithm Stack Overflow with Big array sizes

java

stack-overflow

quicksort

data-structures