QuickSort アルゴリズムの詳細(xì)な説明: 効率的な並べ替えツール

QuickSort は、分割統(tǒng)治戦略に基づいた効率的な並べ替えアルゴリズムです。分割統(tǒng)治法では、問題を小さなサブ問題に分解し、これらのサブ問題を個別に解決し、サブ問題の解を組み合わせて最終的な解を取得します。クイック ソートでは、配列の分割點を決定するパーティション要素を選択することによって配列が分割されます。分割する前に、分割要素の位置が、それより大きい要素の前、小さい要素の後に配置されるように再配置されます。左右の部分配列は、各部分配列に要素が 1 つだけ含まれるまでこの方法で再帰的に分割され、その時點で配列がソートされます。

クイックソートの仕組み

例として、次の配列を昇順に並べ替えてみましょう:

ステップ 1: ピボット要素を選択します

最後の要素をピボットとして選択します:

ステップ 2: ピボット要素を再配置します

ピボット要素を、それよりも大きい要素の前と、それより小さい要素の後に配置します。これを行うには、配列を反復(fù)処理し、ピボットとその前の各要素を比較します。ピボットより大きい要素が見つかった場合は、その要素に対する 2 番目のポインターを作成します:

ピボットより小さい要素が見つかった場合は、それを 2 番目のポインターと交換します。

このプロセスを繰り返し、ピボットより大きい次の要素を 2 番目のポインターに設(shè)定し、ピボットより小さい要素が見つかった場合は交換します。

配列の最後に到達(dá)するまでこのプロセスを続けます:

要素の比較が完了したら、ピボットより小さい要素が右に移動され、ピボットを 2 番目のポインターと交換します。

ステップ 3: 配列を分割する

パーティションインデックスに従って配列を分割します。配列を arr[start..end] として表す場合、配列をパーティションで分割することで、左側(cè)の部分配列 arr[start..partitionIndex-1] を取得できます。右側(cè)のサブ配列 arr[partitionIndex 1..end]。

各部分配列に要素が 1 つだけ含まれるまで、この方法で部分配列の分割を続けます。

この時點で、配列はソートされます。

クイックソートコードの実裝

import java.util.Arrays;

public class QuickSortTest {
    public static void main(String[] args){
        int[] arr = {8, 6, 2, 3, 9, 4};
        System.out.println("未排序數(shù)組: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length-1);
        System.out.println("已排序數(shù)組: " + Arrays.toString(arr));
    }

    public static int partition(int[] arr, int start, int end){
        // 將最后一個元素設(shè)置為樞軸
        int pivot = arr[end];
        // 創(chuàng)建指向下一個較大元素的指針
        int secondPointer = start-1;

        // 將小于樞軸的元素移動到樞軸左側(cè)
        for (int i = start; i < end; i++){
            if (arr[i] < pivot){
                secondPointer++;
                // 交換元素
                int temp = arr[secondPointer];
                arr[secondPointer] = arr[i];
                arr[i] = temp;
            }
        }
        // 將樞軸與第二個指針交換
        int temp = arr[secondPointer+1];
        arr[secondPointer+1] = arr[end];
        arr[end] = temp;
        // 返回分區(qū)索引
        return secondPointer+1;
    }

    public static void quickSort(int[] arr, int start, int end){
        if (start < end){
            // 找到分區(qū)索引
            int partitionIndex = partition(arr, start, end);
            // 遞歸調(diào)用快速排序
            quickSort(arr, start, partitionIndex-1);
            quickSort(arr, partitionIndex+1, end);
        }
    }
}

コード解釈

quickSort メソッド: まず partition メソッドを呼び出して配列を 2 つの部分配列に分割し、次に quickSort を再帰的に呼び出して左右の部分配列を並べ替えます。このプロセスは、すべての部分配列に要素が 1 つだけ含まれるまで続き、その時點で配列がソートされます。

partition メソッド: 配列を 2 つのサブ配列に分割します。まずピボットと次に大きい要素へのポインタを設(shè)定し、次に配列を反復(fù)処理して、ピボットよりも小さい要素を左に移動します。その後、ピボットを 2 番目のポインターと交換し、パーティションの位置を返します。

上記のコードを?qū)g行すると、コンソールに次の內(nèi)容が出力されます:

ソートされていない配列: [8, 6, 2, 3, 9, 4] ソートされた配列: [2, 3, 4, 6, 8, 9]

時間計算量

最良のケース (O(n log n)): 最良のケースは、ピボットが毎回配列を 2 つのほぼ等しい部分に分割する場合に発生します。

平均的なケース (O(n log n)): 平均的なケースでは、ピボットは配列を 2 つの等しくない部分に分割しますが、再帰の深さと比較の數(shù)は依然として n log n に比例します。

最悪のケース (O(n2)): 最悪のケースは、ピボットが常に配列を非常に不均等な部分に分割する場合に発生します (たとえば、一方の部分には 1 つの要素のみが含まれ、もう一方の部分には n-1 個の要素があります)。これは、たとえば、配列を逆順にソートし、ピボットの選択が適切でなかった場合に発生する可能性があります。

空間複雑度 (O(log n)): クイック ソートは通常、インプレースで実裝され、追加の配列は必要ありません。

以上がクイック ソート アルゴリズムを理解する (Java の例付き)の詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。