使用Quicksort Java实现的Stackoverflow

一尘不染

使用Quicksort Java实现的Stackoverflow

algorithm

在Java中实现quicksort时遇到一些问题。运行此程序时出现stackoverflow错误，但我不确定原因。如果任何人都可以指出错误，那就太好了。

si是起始索引。ei是结束索引。

public static void qsort(int[] a, int si, int ei){

    //base case
    if(ei<=si || si>=ei){}


    else{ 
        int pivot = a[si]; 
        int length = ei - si + 1; 
        int i = si+1; int tmp;

        //partition array 
        for(int j = si+1; j<length; j++){
            if(pivot > a[j]){
                tmp = a[j]; 
                a[j] = a[i]; 
                a[i] = tmp;

                i++; 
            }
        }

        //put pivot in right position
        a[si] = a[i-1]; 
        a[i-1] = pivot;

        //call qsort on right and left sides of pivot
        qsort(a, 0, i-2); 
        qsort(a, i, a.length-1); 
    }
}

阅读 242

2020-07-28

共1个答案

一尘不染

首先，您应该按照Keith的建议修复qsort递归调用的边界，因为否则，您总是会一遍又一遍地对整个数组进行排序。您必须调整分区循环：j是一个索引，从子数组的开始到其结尾（包括最后一个元素）。因此，您必须从si
+1循环到ei（包括ei）。

这是正确的代码。我运行了一些测试用例，似乎还不错。

    public static void qsort(int[] a, int si, int ei){
    //base case
    if(ei<=si || si>=ei){}

    else{ 
        int pivot = a[si]; 
        int i = si+1; int tmp;

        //partition array 
        for(int j = si+1; j<= ei; j++){
            if(pivot > a[j]){
                tmp = a[j]; 
                a[j] = a[i]; 
                a[i] = tmp;

                i++; 
            }
        }

        //put pivot in right position
        a[si] = a[i-1]; 
        a[i-1] = pivot;

        //call qsort on right and left sides of pivot
        qsort(a, si, i-2); 
        qsort(a, i, ei); 
    }
}

2020-07-28