クイックソートは、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、右）; }}