クイック ソート アルゴリズムを理解する (Java の例付き)

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

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

クイックソートの仕組み

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

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

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

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

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

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

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

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

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

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

パーティションインデックスに従って配列を分割します。配列を arr[start..end] として表す場合、配列をパーティションで分割することで、左側の部分配列 arr[start..partitionIndex-1] を取得できます。右側のサブ配列 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("未排序数组: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length-1);
        System.out.println("已排序数组: " + Arrays.toString(arr));
    }

    public static int partition(int[] arr, int start, int end){
        // 将最后一个元素设置为枢轴
        int pivot = arr[end];
        // 创建指向下一个较大元素的指针
        int secondPointer = start-1;

        // 将小于枢轴的元素移动到枢轴左侧
        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;
        // 返回分区索引
        return secondPointer+1;
    }

    public static void quickSort(int[] arr, int start, int end){
        if (start < end){
            // 找到分区索引
            int partitionIndex = partition(arr, start, end);
            // 递归调用快速排序
            quickSort(arr, start, partitionIndex-1);
            quickSort(arr, partitionIndex+1, end);
        }
    }
}

コード解釈

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

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

上記のコードを実行すると、コンソールに次の内容が出力されます:

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

時間計算量

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

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

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

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

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