クイックソートは、1962年にCrahoareによって提案された一種の分割交換ソートです。この方法の基本的なアイデアは次のとおりです。
1.最初に、シーケンスから参照番号として数値を取得します。
2。パーティションプロセスでは、この数値をこの数値よりも大きく右に置き、すべての数値を左以下に配置します。
3.各間隔に1つの数値しかなくなるまで、左と右の間隔の2番目のステップを繰り返します。
アルゴリズムには明確なアイデアがありますが、インターバル分割プロセス中に境界値がうまく処理されない場合、バグを引き起こすのは簡単です。以下は、間隔分割コードの執筆を導くための2つの明確な考え方です。
最初のタイプの思考は、いわゆるピット掘削方法思考です。以下は、例を分析して、ピット掘削方法のプロセスを分析するためです。
たとえば、配列を使用して、間隔の最初の番号を参照番号として取得します。
最初は、左= 0;右= 9; x = a [左] = 72
[0]の数はXに保存されているため、アレイA [0]の穴を掘ると理解でき、他のデータはここで入力できます。
右から始めて、多くの<= xを探します。明らかに、右= 8の場合、条件が満たされた場合、[8]を掘り出し、前のピットA [左]に記入します。このようなピットA [0]は解決されますが、新しいピットA [8]が形成されます。どうすればいいですか?簡単に、ピットA [8]に記入する番号を見つけます。今回は、左から始めてXより大きい数を見つけます。左= 3の場合、条件を満たし、[3]を掘り出し、前のピットA [右]で埋めます。
配列は次のようになります
上記の手順を繰り返すと、最終配列が次の形式になります。
[5]の前の数値はそれよりも小さく、[5]の後の数値はそれよりも大きいことがわかります。 [5]のピットにxを入力すると、データは次のようになります。
したがって、2つのサブインターバルA [0…4]と[6…9]について、上記の手順を繰り返します。
掘られた穴の数の要約
1。i= l; j = r;参照番号を掘り出して、最初のピットA [i]を形成します。
2。J - 前から前から前から、それよりも小さい数を見つけ、この数字を掘り出し、前のピットA [i]に記入します。
3。I++は、それよりも前から後ろまで大きい数字を見つけ、それを見つけた後、この数字を掘り出して、前のピットA [J]に記入します。
4。I== jまで手順2と3を繰り返し、参照番号を[i]に記入します。
このパーティション方法に従って、Javaコードは次のように迅速にソートされます。
パブリッククラスパーティション{ / ** *ベース部門に基づいて、小さな部門は左側にあり、大きなものは右側にあり、シーケンス全体を注文する必要はありません。 int right = ary.length -1; int leftpoint = left、rightpoint =右; while(true){//左と右に同時に右に分割して、左から右に、while(leftpoint <右&& ary [leftpoint ++] <base); //左のポイントは右またはary [左下]>ベースがループを停止するwhile(rightpoint> = left && ary [rightpoint-]> base); //逆のSystem.out.println( "左側に交換する必要があるインデックス:" +(leftpoint-1)); system.out.println( "右に交換する必要があるインデックス:"+(rightpoint+ 1)); //条件を満たさない2つのインデックスは、上記で取得されます。つまり、(左ポイント-1 <右ポイント + 1){// swap(ary、leftpoint -1、rightpoint + 1)の場合、交換する必要がある2つのインデックスが取得されます。 util.printarray(ary);左ポイント=左;正しいポイント=右; } else {break; }}} private static void swap(int [] ary、int a、int b){int temp = ary [a]; ary [a] = ary [b]; ary [b] = temp; } public static void main(string [] args){int [] ary = util.genereTintarray(10); System.out.println( "Original Sequence:"); util.printarray(ary);ソート(ary、5); System.out.println( "sorted:"); util.printarray(ary); }}結果:
元のシーケンス:[2、8、4、3、7、7、5、1、9、0、6]左側の交換のインデックス:1右側の交換インデックス:8 [2、0、4、3、7、5、1、9、8、6]左で交換するインデックス:4 [2、0、4、4、3、5、5、7、8、8、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、ソート:[2、0、4、3、1、5、7、9、8、6]
間隔分割の別のガイド考え:
アレイの最初の要素を間隔値として使用し、図に示されている結果が形成されるまで、2番目の要素から分割します。
次に、l <t間隔の正しい境界値とtを交換して、次の結果を形成します。
このようにして、次のようにクイックソートコードを書くことができます。
public void qsort(int array []、int left、int right){if(left <右){int key = array [左]; int high = right; int low =左+1; while(true){while(low <= high && array [low] <= key)low ++; while(low <= high && array [high]> = key)high-; if(low> high)break;スワップ(配列、低、高); }スワップ(配列、左、高); PrintArray(配列); QSORT(配列、左、High-1); QSORT(アレイ、ハイ+1、右); }}