このクイック並べ替えを試してください

第 5 章では、
と呼ばれる単純な分類方法について説明しました。 バブル仕分け。そのとき、
があると述べられました。 評価が大幅に向上しました。ここでは、最も優れたものの 1 つであるクイック ソート (クイックソート) のバージョンを開発します。
C.A.R. によって発明され、命名された簡単な分類。 Hoare は、現在利用可能な最高の汎用分類アルゴリズムです。クイック ソートの最良の実装は再帰に基づいているため、第 5 章ではそれを示すことができませんでした。私たちが開発するバージョンは文字の配列を分類しますが、ロジックはあらゆるタイプのオブジェクトを分類するように適合させることができます。
クイックソートはパーティションの考え方に基づいています。一般的な手順には、比較と呼ばれる値の選択と、配列を 2 つのセクションに分割することが含まれます。パーティション値以上のすべての要素が一方の側に挿入され、小さい要素はもう一方の側に挿入されます。このプロセスは、配列がソートされるまで、残りのセクションごとに繰り返されます。たとえば、fedacb 配列が与えられ、d 値を比較として使用すると、クイック ソートの最初のパスで配列が次のように再配置されます。

初期 f e d a c b
パッセージ 1 b c a d e f

このプロセスはセクションごとに繰り返されます (つまり、bca と def)。ご覧のとおり、このプロセスは本質的に再帰的であり、実際、クイック ソートの最もクリーンな実装は再帰的です。
比較値は 2 つの方法で選択できます。ランダムに選択することも、配列から取得した小さな値のセットの平均を見つけることによって選択することもできます。最適な分類を取得するには、値の範囲のちょうど中央にある値を選択する必要があります。ただし、ほとんどのデータセットでこれを行うのは簡単ではありません。最悪のケースは、選択した値が一方の端にある場合です。それでも、クイックソートは正しく実行されます。
私たちが開発するクイック ソートのバージョンは、配列の中央の要素を比較として選択します。

QSDemo.java を参照してください。

クイックソート:

• 最も効率的で広く使用されている分類アルゴリズムの 1 つ。
• C.A.R.によって発明されました。ホア。
• パーティションの概念に基づいており、配列は再帰的に並べ替えられるセクションに分割されます。
• バブルソートや他の単純な方法よりも効率的です。

操作:

• 比較値 (ピボット):
• 値が参照 (ピボット) として選択され、配列はその値を中心に編成されます。
• ピボットより小さい要素は一方の側に配置され、大きな要素はもう一方の側に配置されます。
• 配列が完全にソートされるまで、このプロセスがセクションごとに再帰的に繰り返されます。

クイックソート

QSDemo

以上がこのクイック並べ替えを試してくださいの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。