Java ソートアルゴリズムの概要 (VII): クイックソート

クイックソートはバブルソートの改良版です。その基本的な考え方は、ソートパスを通じて、ソートするデータが 2 つの独立した部分に分割され、一方の部分のすべてのデータがもう一方の部分のすべてのデータよりも小さくなり、その後、この方法に従って 2 つの部分のデータが別々にすばやくソートされるというものです。ソートプロセス全体を再帰的に実行して、データ全体を順序付けられたシーケンスに変換できます。クイックソートは不安定で、O(log(n)) の追加スペースを必要とし、時間計算量は O(nlog(n)) であり、適応性がありません。

クイックソートには、言及する価値のあるバリエーションがいくつかあります。以下に簡単に紹介します。

ランダム化されたクイックソート:クイックソートの最悪のケースは、各パーティションのピボットの選択に基づきます。基本的なクイックソートでは、最初の要素がピボットとして選択されます。このように、配列がすでに順序付けられている場合、各分割は最悪の結果になります。一般的な最適化方法は、要素をメイン要素としてランダムに選択するランダム化アルゴリズムです。この場合、最悪のケースは依然として O(n^2) ですが、最悪のケースはもはや入力データに依存せず、ランダム関数の評価が不十分なために発生します。実際、クイックソートをランダム化して理論上の最悪のケースを得る確率は 1/(2^n) だけです。したがって、ランダム化クイックソートは、ほとんどの入力データに対して予想される時間計算量 O(nlogn) を達成できます。ある先輩が素晴らしい要約をしてくれました。「ランダムクイックソートは、人の性格のニーズを一生涯満たすことができます。」

ランダム化クイックソートの唯一の欠点は、入力データに同一データが大量に存在すると、ランダム化の効果が直接的に弱まってしまうことです。極端なケース、つまり n 個の同一の数字をソートする場合、ランダムクイックソートの時間計算量は間違いなく O(n^2) に削減されます。解決策は、ピボットを交換せずにそのままの状態でスキャンすることです。

バランスクイックソート: 毎回、中央値をキーデータとして表すことができる要素を選択し、通常のクイックソートの原則に従って比較、置換、再帰を実行します。一般的に、このデータを選択する方法は、開始データ、終了データ、中間データを取得し、比較して中央値を選択することです。この3つの値を取る利点は、実際の問題（情報科学のコンテストなど）では、近似連続データや反転データが出現する可能性が高いことです。この場合、真ん中のデータが必然的に中央値になり、実は近似中央値でもあります。中央が大きく両側が小さい（またはその逆）データに遭遇し、取得した値が最大値に近い場合、少なくとも2つの部分を分離できるため、実際の効率は約2倍になり、データを少し乱して縮退構造を破壊することが有益です。

外部クイックソート: 通常のクイックソートとは異なり、キーデータはバッファです。まず、前と次の M/2 要素がバッファに読み込まれ、バッファ内のこれらの要素がソートされます。次に、ソートされた配列の先頭 (または末尾) から次の要素が読み込まれます。この要素がバッファ内の最小の要素よりも小さい場合は、最初の空きスペースに書き込まれます。この要素がバッファ内の最大の要素よりも大きい場合は、最後の空きスペースに書き込まれます。それ以外の場合は、バッファ内の最大または最小の要素が配列に書き込まれ、バッファに配置されます。すでに順序付けされた中間データの再配置を避けるため、最大値はこれらのキーデータより低く、最小値はこれらのキーデータより高く設定してください。完了後、配列の中央のスペースを空ける必要があり、バッファは配列の中央のスペースに書き込まれます。次に、小さい外側の部分を再帰的にソートし、他の部分を循環的にソートします。

3 方向基数クイックソート (マルチキークイックソート、マルチキークイックソートとも呼ばれます) : 基数ソート (一般的な文字列比較ソートは基数ソートであるなど) とクイックソートの特性を組み合わせたもので、文字列ソートに比較的効率的なアルゴリズムです。このアルゴリズムによってソートされる配列の要素には、文字列などのマルチキーという特性があり、各文字はキーとみなすことができます。アルゴリズムは、ソートされた配列内の要素をキーデータとしてランダムに選択するたびに、まずこの要素の最初のキー (文字) のみを考慮し、次にキーを比較して、他の要素をキーデータより小さい、等しい、大きい 3 つの部分に分割します。次に、このキーの位置に基づいて「より小さい」部分と「より大きい」部分を再帰的にソートし、次のキーに基づいて「等しい」部分をソートします。

コード実装:

公共 クラスクイックソート{
公共 静的  void sort(比較可能なデータ[]、 int low、 int high) {
 // ピボット要素。通常は最初の要素に基づいて分割されます 
 int i = 低い;
整数j = 高い;
 （低<高）の場合{
 // 配列の両端から中央まで交互にスキャンします 
比較可能な pivotKey = data[low];
 // ポインタ i、j をスキャンします。i は左から始まり、j は右から始まります 
 i < j である間{
 i < j && data[j].compareTo(pivotKey) > 0の場合
j--;
 } // 終了 
もし（i < j）{
 // ピボット要素より小さい要素を左に移動する 
データ[i] = データ[j];
私は++;
 } // 終了 
 i < j && data[i].compareTo(pivotKey) < 0の場合
私は++;
 } // 終了 
もし（i < j）{
 // ピボット要素より大きい要素を右に移動する 
データ[j] = データ[i];
 j--;
 } // 終了 
 } // 終了 
 // ピボット要素を正しい位置に移動する 
データ[i] = pivotKey;
 // サブリストの前半を再帰的にソートする 
ソート(データ、low、i - 1 );
 // サブリストの後半部分を再帰的にソートする 
ソート(データ、i + 1 、高);
 } // 終了 
 } // ソート終了 
公共 静的  void main(String[] args) {
 // JDK1.5以降では、基本データ型は自動的にボックス化されます 
 // intやdoubleなどの基本型のラッパークラスはComparableインターフェースを実装しています 
比較可能[] c = { 4 、 9 、 23 、 1 、 45 、 27 、 5 、 2 };
ソート(c, 0 , c.length - 1 );
 (比較可能なデータ: c) {
 System.out.println(データ);
 }
 }
 }