クイックソートは、大まかなアイデアはあるので、長い間私を悩ませてきましたが、コードを書くときに常にさまざまな問題が発生し、それをデバッグするのは個人的にはまだ困難です。ある程度の難易度があり、仕事と怠惰のせいでデバッグできなかったエラーが長い間放置されていましたが、今日ついにリリースされました。まだ少し興奮しています。少し説明。
素早い並べ替えを学ぶには、まず分割統治法を学ぶ必要があります。分割統治の考え方は、順序が異なる一連の数値を与えることです (数値は仮定であり、他のオブジェクトである場合もあります)。もちろん、メソッドのパラメータは自分で定義できます (整数の配列があるとします)。それを彼に渡します。中間の数値である分割統治法は、指定された中央の数値に基づいてこれらの数値を 2 つの部分に分割します。1 つの部分は中央の数値の左側に、もう 1 つの部分はこの数値を右側に配置します。分割点、両側の数値はまだ順序が狂っています。私がそれを定義した方法は次のとおりです。
//left は配列の分割統治部分の左端点であり、right は配列の分割統治部分の合計端点です。たとえば、長さが 10 の配列の場合です。最初の 5 つの整数を除算して征服したいので、0 または 4 を public int signalFenZhi(int left,int right){ if(left<0||left>n-1||right<0||right> として渡すことができます) n-1){ return -1; } int temp = テスト [左]; j=右; int i=左; while(i<j){ while(test[j]>=test[left]&&i<j){ } while(test[i]<=test[left] &&i<j){ i++; } if(i<j){ テスト [i]=テスト[j] } } if(i==j); = テスト[i]; test[i]=test[left]; test[left]=temp; } for(int m=0;m<n;m++){ System.out.print(test[m]+" "); ; }もちろん、中央の数値をパラメータとして渡すこともできます。ここでは、渡された左側の数値を除算数値として使用します。
分割統治を理解すると、簡単な並べ替えは簡単になります。つまり、2 つの部分に分割された数値をすべての数値が揃うまで分割して統治することになります。コードは次のとおりです。
public void QuickSort(int left,int right){ if(right-left<1){ return ; }else{ int point = this.signalFenZhi(left, right); //if( point!=left&&point!=right){quickSort(left,point-1); //} }クイックソートの効率は数あるソートアルゴリズムの中でも優れており、時間計算量は O(N*log2n) ですが、分割統治の分割点を適切に選択しないと、時間計算量は (n の 2 乗) に減少します。 )、この配列がたまたまソートされ、毎回渡される一番左の数値を取得する場合、効率が非常に低くなるため、すべてのオプションをテストすると、この状況を回避する必要があります。時間なので、妥協的な方法は、左端の数値と右端の数値に中央の数値を加算し、その中の数値を除算値として使用することです。上記の方法に基づいて、修正されたコードは次のようになります。しかし、私がそれを終えた後、このアプローチはあまり良くありませんでした。分割統治法として分割値を渡す方が良いでしょう。しかし、私は基本的に同じです。
パッケージ com.jll; パブリック クラス FenZhi { int[] テスト; int n=10; テスト = new int[10]; =(int)(Math.random()*100)+1; System.out.print(test[i]+" ") } public FenZhi(int) n){ if(n>0){ this.n=n; test = new int[n]; for(int i=0;i<n;i++){ test[i]=(int)(Math.random ()*100)+1; } } } public int signalFenZhiMajorizationFirst(int left,int right){ if(left<0||left>n-1||right<0||right>n-1||left>=right){ return -1 } if(right-left>=2){ int middle = (右+左)/2; if(テスト[左]>テスト[中央]){ int 温度 = テスト[左] = 温度; if(テスト[左]>テスト[右]){ int 温度 = テスト[左]; テスト[右]; } if(テスト[中央]>テスト[右]; ){ int temp = テスト[中央] = テスト[右]; } int 温度 = テスト[中央] = テスト[左]; = temp; int j=right-1; int i=left+1; while(test[j]>=test[left]&&i<j) { j--; ]<=test[left]&&i<j){ i++; } if(i<j){ temp = test[i]=test[j]; } if( i==j){ temp = テスト[i]=テスト[左]; } /*if(i==j){ テスト[中央]=テスト[i] ]; test[i]=temp; }*/ /*for(int m=0;m<n;m++){ System.out.print(test[m]+" ");それ以外 { if(test[right]<test[left]){ int temp = test[right]; test[left] } } return right; ,int right){ if(right-left<1){ return ; }else{ int point = this.signalFenZhiMajorizationFirst(left, right);は: "+point);quickSortMajorizationFirst(left,point-1);quickSortMajorizationFirst(point+1,right); } } public static void main(String[] args) { FenZhi f = new FenZhi(); System.out. println(f.signalFenZhiMajorizationFirst(0, 9)); f.quickSortMajorizationFirst(0,fn-1); //f.quickSort(0,f.test.length-1); for(int i:f.test){ System.out.print(i+" "); }}コードは次のように実行されます。
95 40 64 18 78 23 73 84 40 ポイントは:4 ポイントは:1 ポイントは:3 ポイントは:7 ポイントは:6 ポイントは:918 23 40 40 64 73 78 84 95
以上が私が学んだことですので、今後の参考のために記録しておきます。