代码之家  ›  专栏  ›  技术社区  ›  artemis Roberto

堆栈溢出错误时快速排序算法失败

  •  -1
  • artemis Roberto  · 技术社区  · 6 年前

    我正在开发一个修改版的快速排序,它使用了 ((lowIndex + highIndex) / 2)

    我的代码在下面。但是,无论何时运行它,都会出现以下错误:

    start ARRAY
    1
    2
    10
    9
    3
    4
    8
    7
    5
    6
    Exception in thread "main" java.lang.StackOverflowError
            at newQuickSort.quicksort(newQuickSort.java:37)
            at newQuickSort.quicksort(newQuickSort.java:39)
    

    at newQuickSort.quicksort(newQuickSort.java:39) 是重复的。

    从本质上说,我只是想把配分函数改为使用三分之一的中位数,而不是真正接触快速排序算法,只是配分函数。

    我不太清楚为什么会发生这个错误,尽管我引用了以下内容:

    任何建议都会有帮助,谢谢!

    public class newQuickSort{ 
    
        static int count;
    
        static void move(int myArray[], int a, int b){
            int temp;
            temp = myArray[a];
            myArray[a] = myArray[b];
            myArray[b] = temp;
        } //end move
    
        //Create the partition function
        static int partition(int myArray[], int p, int r){
            int medIndex = (p+r) / 2;
            int pivot;
    
                if (myArray[p] > myArray[medIndex]){
                    move(myArray, p, medIndex); 
                }else if (myArray[p] > myArray[r]){
                    move(myArray, p, r);
                }else if (myArray[medIndex] > myArray[r]){
                    move(myArray, medIndex, r);
                }
                //end if checks
    
                //now set proper movements
                move(myArray, medIndex, r-1);
                //set pivot
                pivot = myArray[r-1];
                //return pivot for which to partition around
                return pivot;
        } //end partition 
    
        static void quicksort(int myArray[], int p, int r){ 
            if (p < r){
            checkCount += 1; 
                int partition = partition(myArray, p, r); 
                quicksort(myArray, p, partition-1); 
                quicksort(myArray, partition+1, r); 
            } //end if 
        } //end quicksort
    
        public static void main (String[] args){
            int testarray[] = {1,2,10,9,3,4,8,7,5,6};
           // int testarray[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
            System.out.println("start ARRAY");
            for (int i = 0; i < testarray.length; i++){
                System.out.println(testarray[i]);
            } //end for
    
            int p = 0;
            int r = testarray.length-1;
            newQuickSort mySort = new newQuickSort();
            mySort.quicksort(testarray, p, r);
    
            System.out.println("end ARRAY");
            for (int j = 0; j < testarray.length; j++){
                System.out.println(testarray[j]);
             } //end for
    
        }
    }
    
    1 回复  |  直到 6 年前
        1
  •  1
  •   rici    6 年前

    你的 partition 函数返回 价值 quicksort )正在期待 指数 轴心的位置。

    递归的终止取决于索引范围内的分区点。

    一旦你解决了这个问题,考虑优化 快速排序 要尽量减少堆栈使用:

    1. 然后循环以继续更大的范围。

    这保证了递归深度不超过log 2 N。