计算器与快速排序的Java实现 [英] Stackoverflow with Quicksort Java implementation

问题描述

有实现快速排序在java中的一些问题。我得到一个计算器错误，当我运行这个程序，我不知道是什么原因。如果任何人都可以指出错误，这将是巨大的。

Si为起始索引。 EI是结束索引。

 公共静态无效的qsort（INT []一，INT SI，诠释EI）{

    //基本情况
    如果（EI＆LT; = SI || SI＆GT; = EI）{}


    其他{
        INT支点= A [SI];
        INT长度= EI  -  SI + 1;
        INT I = SI + 1; INT TMP;

        //分隔阵列
        对于（INT J = SI + 1; J＆LT;长度; J ++）{
            如果（枢轴＆gt;一种[J]）{
                TMP = A [J]。
                一个[J] = A [1];
                A [1] = tmp目录;

                我++;
            }
        }

        //在合适的位置把支点
        一个[SI] = A [1-1];
        一个[I-1] =枢轴;

        //调用的qsort上支点的左右两侧
        的qsort（一，0，I-2）;
        的qsort（A，I，则为a.length-1）;
    }
}
 

解决方案

首先，你应该解决的qsort递归调用的边界所建议的基思，否则你总是一遍又一遍的排序整个数组。在你必须调整你的分区循环：j是一个指数，从子阵列到它的结束的开始会（包括最后一个元素）。所以，你必须从SI环+ 1 EI（其中EI）。

所以这是纠正code。我跑了几个测试案例，它似乎排序就好了。

 公共静态无效的qsort（INT []一，INT SI，诠释EI）{
    //基本情况
    如果（EI＆LT; = SI || SI＆GT; = EI）{}

    其他{
        INT支点= A [SI];
        INT I = SI + 1; INT TMP;

        //分隔阵列
        对于（INT J = SI + 1; J＆LT; = EI; J ++）{
            如果（枢轴＆gt;一种[J]）{
                TMP = A [J]。
                一个[J] = A [1];
                A [1] = tmp目录;

                我++;
            }
        }

        //在合适的位置把支点
        一个[SI] = A [1-1];
        一个[I-1] =枢轴;

        //调用的qsort上支点的左右两侧
        的qsort（一个，SI，I-2）;
        的qsort（A，I，EI）;
    }
}
 

Having some problems implementing quicksort in java. I get a stackoverflow error when I run this program and I'm not exactly sure why. If anyone can point out the error, it would be great.

si is the starting index. ei is the ending index.

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

解决方案

First you should fix the bounds of the qsort recursive call as suggested by Keith, since otherwise you're always sorting the whole array over and over again. The you must adjust your partition loop: j is an index, going from the beginning of the subarray to the end of it (including the last element). So you must loop from si + 1 to ei (including ei).

So this is the corrected code. I ran a few test cases and it seems to sort just fine.

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

这篇关于计算器与快速排序的Java实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！