java - 具有小输入集的 java 中的堆栈溢出错误

Question

我正在尝试用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);
    }

}

}

Answer 1

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实际上不是 [i, j] 范围内的元素，循环开始时的元素搜索可能会变得疯狂。特别是pivot可能是一个非常小的值，小于该范围内的任何值。 i搜索将立即终止(i == l 保持其开始的方式)，而 j搜索将远远超出 i ，这意味着if也不会被输入，i仍然没有改变，主循环终止。因为i不变，i<h仍然为真(假设 l<h 是)，并且您使用与刚才完全相同的参数进入递归调用，这意味着下一个调用将执行与当前调用完全相同的操作，以无限递归结束。