バブルソート、選択選別などのアルゴリズムと比較して、特定のアルゴリズムの原則とクイックソートの実装は困難です。迅速な並べ替えをよりよく理解するために、例の形式で詳細に迅速な並べ替えのアルゴリズム原理を説明します。以前のソートアルゴリズムでは、それを説明する例として、5人のアスリートの高さ並べ替えの問題を使用します。高速ソートの特性をよりよく反映するために、ここにさらに3人のアスリートを追加します。例の8人のアスリートとその高さ情報は次のとおりです(F、G、Hは新しいアスリートです):A(181)、B(169)、C(187)、D(172)、E(163)、F(191)、G(189)、H(182)
以前のソートアルゴリズムでは、これらの並べ替えはすべてコーチによって行われました。アスリートの数が増えた今、コーチはまた、休憩をとる機会を得たいと思っているので、コーチは2人のアシスタントに電話をかけ、2人のアシスタントに8人のアスリートの高さを左から右、低から高から高く整理するように頼みました。
クイックソートメソッドのアルゴリズムの原則によれば、2人のアシスタントは、下の図に示すように、アスリートのアレンジメントの両側に立っています。
最初に、アシスタント1はアレンジからアスリートを選択します(通常、左側の最初のアスリートまたはミドルアスリートを選択します)、ここでアスリートA(181)を選択します。ソートは左から右から低いためであるため、アシスタント1には(181)(181)(181)よりも高さが小さいアスリートが比較のベンチマークとして使用されます。このラウンドのすべての比較は、最初に選択されたアスリートA(181))と比較されます。
さらに、クイックソートの最初のラウンドの詳細な図を参照しましょう。
選別および検索プロセス中に2人のアシスタントが会うと、現在のラウンドの比較が停止し、最初に選択されたアスリートA(181)が2人のアシスタントが出会う空きスペースに配置されます。
クイックソートでは、2人のアシスタントが出会ったとき、このソートのラウンドは終了します。この時点で、2人のアスリートが分割ポイントとして出会った位置A(181)を使用して、左のアスリートは(181)よりも小さいアスリートであり、右側のアスリートはAよりも大きいアスリートであることがわかりました。この時点で、(181)の左側と右側に2つの並べ替えを分離します。上記の2人のアシスタントの並べ替え方法を使用して両側のアレンジメントを並べ替え続けると、複数の配置の後、最終的に必要な並べ替え結果が得られます。
上記は、クイックソートの完全なソート実装プロセスです。クイックソートは、上記の並べ替えルールを使用してアレンジメントを2つのアレンジメントに分割し、2つのアレンジメントを分割する配置がないまで4つのアレンジメントに分割し、最後に必要なソート結果を取得します。
今、私たちはまだJavaコードをプログラムして、クイックソートを使用して上記の8人のアスリートの高さを並べ替えます。
/***指定されたアレイ内の要素のクイックスタートは、開始から終わりまで** @param配列* @param @param @param @paramは、迅速にソートする必要があるアレイ照会の結果のポイントを開始* @param end eand of the array index of the array indexを迅速に並べ替える必要があります*/public static final void Quicksort(int、int、int、assivers assect assionアシスタント2 int i = start、j = endの位置。 int pivot = array [i]; //参照要素として最初の要素をemptyindex = i; //空きスペースの位置インデックスが示され、デフォルトは取得される参照要素の位置です(i <j){//アシスタント2がアシスタント1に遭遇する前に対応する要素を見つけた場合、アシスタント1の「空室」に要素を与え、jは空きスペース配列[emptyindex] = array [emptyindex = j]になります。 } //アシスタント1は、左から右への参照要素よりも大きい要素を探し始めます(i <j && array [i] <= pivot)i ++; (i <j){//アシスタント1がアシスタント2に遭遇する前に対応する要素を見つけた場合、アシスタント2の「空室」に要素を与え、私は空の配列[emptyindex] = array [emptyindex = i]; }} //アシスタント1およびアシスタント2の出会いの後、ループが停止し、初期基準値が最後の空いているアレイ[emptyIndex] = pivot; // =====このクイックソートのラウンドは完了します===== //スプリットポイントIの左側に2つ以上の要素がある場合、再帰呼び出しは(I -Start> 1){QuickSort(Array、0、I -1); } //スプリットポイントjの右側に2つ以上の要素がある場合、再帰呼び出しは、(end -j> 1){QuickSort(array、j + 1、end); }} //メインメソッドpublic static void main(string [] args){// ===== 8人のアスリートの高さを表すクイックソートメソッドを使用して低から高く並べ替え====== // A(181)、B(169)、C(187)、D(172)、E(163)、F(163)、F(191)、G(189)、Hits、Hits、 187、172、163、191、189、182}; //クイックソートメソッドQuickSort(heights、0、heights.length -1)を呼び出します。 //(int height:heights)の出力ソート結果{system.out.println(height); }}上記のJavaコードの実行結果は、次のように出力されます。
163169172181182187189191
注:ローカルな思考の違いにより、上記のクイックソートコードの実装に複数のバリエーションがある場合があります。ただし、どのようなバリエーションがあっても、クイックソートの核となるアイデアは変わりません。
別の実装:一方向スキャン
クイックソートアレイスライシングのための別の一方向スキャンバージョンがあります。特定のステップは、配列の最後の要素をスライス要素として選択し、2つのポインターを設定することです。ポインターIが配列の最初の要素の前の位置を指し、Jは配列の最初の要素を指します。 Jスキャンは、前後にスキャンします。スライシング要素に等しく等しく遭遇した場合は、iを1つに追加してから、指された要素をiとjで交換します。最後に、位置I+1の要素とスライス要素を交換して、配列分割を完了します。コードの実装は次のとおりです。
intパーティション(int [] a、int lo、int hi){int i = lo -1、j = lo; int v = a [hi]; while(j <hi){if(a [j] <= v){swap(a、++ i、j); } j ++; } swap(a、i + 1、hi); i + 1を返します;}