0

私はまだ初心者で、クイックソートコードを書こうとしています

ここに私のコードがあります

package algo_quicksort;

public class Algo_quicksort {

    public static int partition(int[]A,int p,int r){
        int x=A[p];
        int i=p+1;
        int temp;
        for(int j=p+1;j<r;j++){
            if(A[j]<x){//if A[j] is bigger than the pivot do nothing 
                temp=A[j];
                A[j]=A[i];
                A[i]=temp;
                i++;
            }
        }
        temp=A[p];
        A[p]=A[i-1];
        A[i-1]=temp;
        return i-1;
    }

    public static void quickSort(int[]A,int starPos,int length){
        if(length==1){
            return;
        }
        else{
         if(startPos<length){
        int pivot= partition(A,0,length);
       quickSort(A,startPos,pivot+1);

        quickSort(A, pivot+2,length); 

        }
    }}


    public static void main(String[] args) {
        int a[]={6,5,4,3,2,1};
        System.out.println("A[] after quicksort is: ");

        quickSort(a,0, a.length);
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+"  ");
        }
    }
}

再帰呼び出しでスタック オーバー フロー例外が発生する

理由がわかりませんが、助けていただければ幸いです^_^

4

2 に答える 2

1

このプログラムには多くのバグがあります。私が見つけたいくつかを以下に示します。

  1. starPosあなたは使用しませんquickSort()
  2. 使用しないlength(使用するA.length) でquickSort()
  3. チャールズが言及したピボットの「オーバーレイ」の問題
  4. では、ピボットにある小さいpartition()アイテムの場所を、ピボットにある大きいアイテムと交換する必要があります。そうしないでください。rightleft

おそらくもっとあります。私が行った Ruby でのクイックソートの実装 (Java に移行するのは簡単です) を見て、自分の実装と正しく理解できるまで比較してみてください。ほとんどの人が考えるよりもトリッキーです!

http://alfasin.com/playing-with-ruby/

于 2013-08-05T15:47:22.213 に答える