0

クイックソート用に次のコードを作成しましたが、一意の番号に対してはうまくいっているようです。
ただし、重複が存在する場合は惨めに失敗します。
重複の調整を行う際に助けていただければ幸いです。

class QuickSort{

    public static void sort(int left,int right,int[] data){
            if(right-left <= 0) return;
            int pivot=organize(left,right,data);
            sort(left,pivot-1,data);
            sort(pivot,right,data);
        }

        private static int organize(int left,int right,int[] data){
            int _right=right;
            int _left=left;
            int pivot=(left+right)%2==0?(left+right)/2:(left+right+1)/2;
            //Move the pivot to the extreme right.
            int pivotval=data[pivot];
            swap(pivot,right,data);
            left=left-1;//to adjust teh stating pointer
            while(true){

                while(right > 0 &&  data[--right]>pivotval);
                while(data[++left]<pivotval);
                if(right<=left) break;
                swap(left,right,data);

            }
            swap(left,_right,data);
            return left;
        }

        private static void swap(int left,int right,int[] data){
            int temp=data[right];
            data[right]=data[left];
            data[left]=temp;
        }

public static void main(String[] args){
                int N=Integer.parseInt(args[0]);
            int[] data=new int[N];
            Random r=new Random();
                    for(int i=0 ;i<N;i++)
                data[i]=r.nextInt(N);

                //After populating the array
                QuickSort.sort(0,data.length-1,data);

            }



            }
4

3 に答える 3

0

ピボットを一番右に移動しますが、while ループの後でピボットを元に戻したい場合は、 を呼び出しますswap(left,_right,data);が、左はピボットと等しくなくpivot=(left+right)%2==0?(left+right)/2:(left+right+1)/2;、左は不明です。Hoare-Partition を使いたいようです。ここにあります：

private static int organize(int left,int right,int[] data){
        int pivot=(left+right)%2==0?(left+right)/2:(left+right+1)/2;
        //Move the pivot to the extreme right.
        int pivotval=data[pivot];
        //swap(pivot,right,data);
        left=left-1;//to adjust the stating pointer
        right = right + 1;
        while(true){

            while(right > 0 &&  data[--right]>pivotval);
            while(data[++left]<pivotval);
            if(right<=left) break;
            swap(left,right,data);

        }
        //swap(left,right,data);
        return left;
    }
于 2013-08-11T06:22:37.610 に答える
0

等しい要素で何をするかを決める必要があります。最も簡単な解決策は、それらを片側に投げて右に言うことです。

        while(true){

            while(right > 0 &&  data[--right]>=pivotval);
            while(data[++left]<pivotval);
            if(right<=left) break;
            swap(left,right,data);

        }

ここでの問題は、場合によってはアルゴリズムが非常に遅くなることです。より良いアプローチは、配列の中心でピボット以降に成長する等しい要素の 3 番目の領域を形成することです。

よりシンプルで簡単なアプローチでは、2 つの反復を行います。最初の反復では、ピボットよりも大きな要素をフィルター処理して、配列の右端にグループを形成し、次に、左端に小さな要素のグループを形成します。間にあるものはピボットと同じです。

お役に立てれば。

于 2013-07-12T14:48:24.563 に答える