クイックソートは分割統治アルゴリズムです。分割統治アルゴリズムの設計パラダイムでは、問題をサブ問題に再帰的に分割し、サブ問題を解決し、最後に解決策を組み合わせて最終結果を見つけます。この記事では、QuickSortInに焦点を当てます
この記事では、次のポイントについて説明します。
さぁ、始めよう！
問題をサブ問題に分割する際に留意すべきことの1つは、サブ問題の構造は元の問題の時点では変更されないということです。
分割統治アルゴリズムには3つのステップがあります。
- 分割：問題をサブ問題に分割する
- 征服：サブ問題を再帰的に解決する
- 組み合わせる：ソリューションを組み合わせて最終結果を得る
分割統治パラダイムに基づくさまざまなアルゴリズムがあります。クイックソートとマージソートはその中にあります。
クイックソートの最悪の時間計算量はO（n2）であり、マージソートやヒープソートなどの他の多くのソートアルゴリズムよりも優れていますが、QuickSortの内部ループはほとんどのアーキテクチャで効率的に実装できるため、実際には高速です。実世界のデータ。
クイックソートアルゴリズムの実装について話しましょう。クイックソートアルゴリズムはピボット要素を取り、ピボット要素の周りに配列を分割します。ピボット要素の選択方法に応じて、Quicksotにはさまざまなバリエーションがあります。ピボット要素を選択する方法は複数あります。
- 最初の要素を選ぶ
- 最後の要素を選択してください
- ランダムな要素を選ぶ
- 中央値要素の選択
次に理解しておくべき重要なことは、クイックソートアルゴリズムのpartition（）関数です。ピボット要素を取得して正しい位置に配置し、ピボット要素よりも小さいすべての要素を左に移動し、すべての要素を右に移動するパーティション関数。クイックソートはそうするのに直線的な時間がかかります。
次に、配列はピボット要素から2つの部分に分割され（つまり、ピボットより小さい要素とピボットより大きい要素）、両方の配列がクイックソートアルゴリズムを使用して再帰的に並べ替えられます。
これで、QuickSortアルゴリズムの動作を理解できました。 Javaでクイックソートアルゴリズムを実装する方法を理解しましょう。
クイックソート 関数：
/ *クイックソート関数では、配列を最小および最大のインデックスでソートする必要があります* /
void sort（int arr []、int lowIndex、int highIndex）{// lowIndex = highIndexまでif（lowIndex次に、パーティショニングコードを見て、その動作を理解しましょう。
パーティション コード
パーティショニングコードでは、最後の要素をピボット要素として選択します。配列全体をトラバースします（つまり、この場合は変数jを使用します）。配列内の最後の最小要素を追跡します（つまり、この場合は変数iを使用します）。ピボットよりも小さい要素が見つかった場合は、スワップ電流要素a [j]をarr [i]と移動します。それ以外の場合は、トラバースを続行します。
int partition（int arr []、int lowIndex、int highIndex）{//最後の要素をピボットとして作成intピボット= arr [highIndex] // iを使用してピボットから小さい要素を追跡するinti =（lowIndex-1） for（int j = lowIndex jクイックソートとパーティション関数を理解したので、完全なコードを簡単に見てみましょう。
Java用のEclipseを構成する方法
クイックソート Javaコード
class QuickSort {//パーティションメソッドintpartition（int arr []、int lowIndex、int highIndex）{intピボット= arr [highIndex] int i =（lowIndex-1）for（int j = lowIndex j//ソート方法
void sort（int arr []、int lowIndex、int highIndex）{if（lowIndex//配列を出力するメソッド
static void printArray（int arr []）{int n = arr.length for（int i = 0 i//メインメソッド
public static void main（String args []）{int arr [] = {101、37、68、29、11、5} int n = arr.length QuickSort ob = new QuickSort（）ob.sort（arr、0、 n-1）System.out.println（ 'sorted array'）printArray（arr）}} 出力：
上記のJavaプログラムを実行した後、QuickSortがどのように機能するかとJavaで実装する方法を理解できたはずです。これで、「Javaでのクイックソート」に関するこの記事は終わりです。詳細を知りたい場合は、チェックアウト 信頼できるオンライン学習会社であるEdurekaによる。 EdurekaのJavaJ2EEおよびSOAトレーニングおよび認定コースは、Hibernate＆SpringなどのさまざまなJavaフレームワークに加えて、コアJavaコンセプトと高度なJavaコンセプトの両方についてトレーニングするように設計されています。
質問がありますか？このブログのコメントセクションでそれについて言及してください。できるだけ早くご連絡いたします。