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

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

クイックソートの仕組み

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

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

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

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

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

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

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

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

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

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

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

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

この時(shí)點(diǎn)で、配列はソートされます。

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

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){
        // 將最后一個(gè)元素設(shè)置為樞軸
        int pivot = arr[end];
        // 創(chuàng)建指向下一個(gè)較大元素的指針
        int secondPointer = start-1;

        // 將小于樞軸的元素移動(dòng)到樞軸左側(cè)
        for (int i = start; i < end; i++){
            if (arr[i] < pivot){
                secondPointer++;
                // 交換元素
                int temp = arr[secondPointer];
                arr[secondPointer] = arr[i];
                arr[i] = temp;
            }
        }
        // 將樞軸與第二個(gè)指針交換
        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 つだけ含まれるまで続き、その時(shí)點(diǎn)で配列がソートされます。

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

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

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

時(shí)間計(jì)算量

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

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

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

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

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