有 Java 编程相关的问题?

你可以在下面搜索框中键入要查询的问题!

基于Quicksort Java实现的Stackoverflow算法

在java中实现快速排序时遇到一些问题。当我运行这个程序时,我得到了一个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); 
    }
}

共 (6) 个答案

  1. # 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); 
        }
    }
    
  2. # 2 楼答案

    int partition(int array[], int too_big_index, int too_small_index)
    {
         int x = array[too_big_index];
         int i = too_big_index;
         int j = too_small_index;
         int temp;
         do
         {                 
             while (x <array[j])
            {
                  j --;
            } 
             while (x >array[i])
             {
                  i++;
             } 
              if (i < j)
             { 
                     temp = array[i];    
                     array[i] = array[j];
                     array[j] = temp;
             }
         }while (i < j);     
         return j;           // middle  
    }
    
    void QuickSort(int num[], int too_big_index, int too_small_index)
    {
          // too_big_index =  beginning of array
          // too_small_index = end of array
    
         int middle;
         if (too_big_index < too_small_index)
        {
              middle = partition(num, too_big_index, too_small_index);
              QuickSort(num, too_big_index, middle);   // sort first section
              QuickSort(num, middle+1, too_small_index);    // sort second section
         }
         return;
    }
    
    
    
    void main()
    {
        int arr[]={8,7,13,2,5,19,1,40,12,34};
    
        QuickSort(arr,0,9);
        for(int i=0;i<10;i++)
             System.out.println(arr[i]);
    }
    
  3. # 3 楼答案

    你可以试试这个:

    public void sort(int[] A) {
            if (A == null || A.length == 0)
                return;
            quicksort(A, 0, A.length - 1);
        }
    
        public void quicksort(int[] A, int left, int right) {
            int pivot = A[left + (right - left) / 2];
            int i = left;
            int j = right;
            while (i <= j) {
                while (A[i] < pivot) {
                    i++;
                }
                while (A[j] > pivot) {
                    j--;
                }
                if (i <= j) {
                    exchange(i, j);
                    i++;
                    j--;
                }
            }
    
            if(left < j)
                quicksort(A,left,j);
            if(i < right)
                quicksort(A,i,right);
        }
    
        public void exchange(int i, int j){
            int temp=A[i];
            A[i]=A[j];
            A[j]=temp;
        }
    
        public String toString() {
            String s = "";
            s += "[" + A[0];
            for (int i = 1; i < A.length; i++) {
                s += ", " + A[i];
            }
            s += "]";
            return s;
        }
    

    资料来源:Code 2 Learn: Quick Sort Algorithm Tutorial

  4. # 4 楼答案

    //刚刚为这个实现了tester类,它会工作的

    公共int[]排序(int[]A,int from,int to){

    if(from<to){
        int pivot=partition(A,from,to);
        if(pivot>1)
            sort(A,from, pivot-1);
    
        if(pivot+1<to)
            sort(A, pivot+1, to);
    
    
    }
    
    return array;
    

    }

    公共int分区(int A[],int from,int to){

    while(from < to){
        int pivot=A[from];
    
        while(A[from]<pivot)
            from++;
    
        while(A[to]>pivot)
            to--;
    
    
        if(from<to)   
            swap(A,to,from);
    
    
    
    }
        return to;
    }
    
    private void swap(int A[], int i, int j){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;}
    
  5. # 5 楼答案

    import java.util.Arrays;
    
    
    public class QuickSort {
    
    
        public static int pivot(int[] a, int lo, int hi){
            int mid = (lo+hi)/2;
            int pivot = a[lo] + a[hi] + a[mid] - Math.min(Math.min(a[lo], a[hi]), a[mid]) - Math.max(Math.max(a[lo], a[hi]), a[mid]);
    
            if(pivot == a[lo])
                return lo;
            else if(pivot == a[hi])
                return hi;
            return mid;
        }
    
        public static int partition(int[] a, int lo, int hi){
    
            int k = pivot(a, lo, hi);
            //System.out.println(k);
            swap(a, lo, k);
            //System.out.println(a);
            int j = hi + 1;
            int i = lo;
            while(true){
    
                while(a[lo] < a[--j])
                    if(j==lo)   break;
    
                while(a[++i] < a[lo])
                    if(i==hi) break;
    
                if(i >= j)  break;
                swap(a, i, j);
            }
            swap(a, lo, j);
            return j;
        }
    
        public static void sort(int[] a, int lo, int hi){
            if(hi<=lo)  return;
            int p = partition(a, lo, hi);
            sort(a, lo, p-1);
            sort(a, p+1, hi);
        }
    
        public static void swap(int[] a, int b, int c){
            int swap = a[b];
            a[b] = a[c];
            a[c] = swap;
        }
    
        public static void sort(int[] a){
            sort(a, 0, a.length - 1);
            System.out.print(Arrays.toString(a));
        }
    
        public static void main(String[] args) {
            int[] arr = {5,8,6,4,2,9,7,5,9,4,7,6,2,8,7,5,6};
            sort(arr);
        }
    }
    

    试试这个。这肯定会奏效的

  6. # 6 楼答案

    您可能有一个无限递归错误。从我的快速扫描中不确定,但是

    即使您不这样做,您仍然会在这个实现中使用大量堆栈。足以导致堆栈溢出。如果你用100万个已经分类的项目来称呼它,会发生什么?将它们划分为1和999999项,然后递归。所以你需要100万个堆栈帧来完成这项工作

    有很多方法可以解决这个问题,包括在两个范围中较小的范围上递归,在两个范围中较大的范围上迭代,或者自己在堆数据结构中实现堆栈,等等。不过,你可能想做得更好,因为深堆栈也意味着你正在突破O(n lg n)排序界限

    另外,问题是:

    qsort(a, 0, i-2); 
    qsort(a, i, a.length-1); 
    

    应该是

    qsort(a, si, i-2);
    qsort(a, i, ei);