在java中实现quicksort时遇到一些问题.我运行这个程序时出现*错误,我不确定为什么.如果有人能指出错误,那就太好了.

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); 
    }
}

解决方法:

首先,您应该按照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); 
    }
}