时间戳

首页 > 解决方案 > 对 1000 个随机项目列表进行快速排序时堆栈溢出

java - 对 1000 个随机项目列表进行快速排序时堆栈溢出

问题描述

它适用于 10 到 50 个随机项目列表，但是当我达到 1000 时它变得不稳定，有时会发生堆栈溢出，1000 甚至更糟。代码如下：

public class InPlaceQuickSort {
    int array[] = {};

    public InPlaceQuickSort(int[] consArray) {
        array = consArray;
    }

    public void qsort(int left, int right) {
        int oldRight = right;
        int oldLeft = left;
        int pivot = left;
        while (array[left] <= array[pivot]) { // increase left pointer until bigger than pivot 
            left = left + 1;
            if (left >= array.length) {
                break;
            }
        }
        while (array[right] > array[pivot]) { // decrease right pointer until smaller than pivot 
            right = right - 1;
            if (right == 0) {
                break;
            }
        }
        if (right <= left) {
            swap(pivot,right); // right change to pivot
            if ((oldRight - right) >= 2) { // here we do right chunk if there are 
                qsort(right+1, oldRight);
            }
            if ((right - oldLeft) > 2) { // here we do left chunk if there are 
                qsort(0, right - 1);
            }
        } else {
            swap(left, right); // swap both anomoly 
            qsort(pivot, oldRight);
        }
    } 

    private void swap(int n1, int n2) {
        int tmp = array[n1];
        array[n1] = array[n2];
        array[n2] = tmp;
    }

}

标签： java

解决方案

Java 中默认的最大堆栈深度为 999。

具有讽刺意味的是，如果数据已经排序，则使用最大深度（作为最差的时间复杂度命中）进行快速排序。

尝试通过设置此 VM 参数来增加最大堆栈深度：

-Xss 9999

推荐阅读