0

我正在尝试用java编写快速排序。但是对于非常小的输入集会出现堆栈溢出错误。在 createArray 函数中，我接受 Scanner 对象的输入。

请有人帮助我。

public class quickSort {

static int[] ar;
int number;

public static void main(String args[]) {
    CreatingArray ca = new CreatingArray();
    ar = ca.createArray();
    ca.printArray(ar);
    int len = ar.length;
    sort(0,(len-1));
    System.out.println("");
    System.out.println("Array after QuickSort:");
    ca.printArray(ar);
}

public static void sort(int l,int h) {
    int i=l;
    int j=h;
    int temp =0;
    int pivot = ar[(l + (l+h)/2)];

    while(i <= j) {
        while(ar[i] < pivot) {
            i++;
        }
        while(ar[j] > pivot) {
            j--;
        }
        if (i<=j) {
            temp = ar[i];
            ar[i] = ar[j];
            ar[j] = temp;
            i++;
            j--;
        }   
    }
    if(l<j){
        sort(l,j);
    }
    if(i<h) {
        sort(i,h);
    }

}

}

4

2 回答 2

2 
int pivot = ar[(l + (l+h)/2)];

这条线是错误的。它仅在 时获得中心点l == 0。如果说，l == 4 && h == 7（例如，一个 8 元素数组的上半部分），你会得到4 + (4+7)/2哪个9在边界之外。你真的想要l + (h-l+1)/2。

因此可能发生的第一件事是ArrayIndexOutOfBoundsException，但你永远不会得到它，因为你总是首先在较低的分区上递归并遇到第二个问题。交换if函数末尾的两个 s 以查看实际情况。

可能发生的第二件事是，因为pivot实际上不是 range[i, j]中的元素，所以循环开始时的元素搜索可能会发疯。特别是，pivot可能是一个非常小的值，小于范围内的任何值。搜索将i立即终止（离开i == l它开始的方式），而j搜索将运行超出i，这意味着if也不会输入，i仍然不会改变，并且主循环终止。因为i没有改变，i<h仍然为真（假设l<h是），并且您使用与刚才相同的参数进入递归调用，这意味着下一次调用将执行与当前调用完全相同的操作，以无限递归结束。

于 2013-09-18T10:06:30.373 回答
0

我认为你的递归调用不会结束......用非常小的输入调试你的代码 - 比如3个数字......检查何时以及如何调用sort（）......

于 2013-09-18T10:03:24.093 回答