Java クイック ソート アルゴリズムの時間計算量と空間計算量を分析する

Java クイック ソート関数の時間計算量と空間計算量の分析

Quick Sort (クイック ソート) は比較ベースのソート アルゴリズムであり、配列は 2 つの部分配列に分割されます。 、その後、配列全体がソートされるまで、2 つの部分配列が別々にソートされます。クイックソートの時間の複雑さと空間の複雑さは、このソートアルゴリズムを使用するときに考慮する必要がある重要な要素です。

クイック ソートの基本的な考え方は、要素をピボット (ピボット) として選択し、配列内の他の要素をピボットとの関係に基づいて 2 つのサブ配列に分割することです。 1 つのサブ配列が pivot. 要素以下である場合、もう 1 つのサブ配列の要素はすべて pivot. 要素以上です。次に、2 つの部分配列が再帰的に並べ替えられ、最後にマージされます。

次は、Java で実装されたクイック ソート関数のコード例です。

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int partitionIndex = partition(arr, low, high);
            quickSort(arr, low, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, high);

        return i + 1;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {6, 5, 3, 1, 8, 7, 2, 4};
        int n = arr.length;

        quickSort(arr, 0, n - 1);

        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

クイック ソートの時間計算量は O(nlogn) です。ここで、n は配列の長さです。各パーティションが配列を正確に均等に分割する最良のケースでは、クイック ソートの時間計算量は O(nlogn) です。最悪の場合、つまり各パーティションが配列の最小または最大の要素をピボット要素として見つける場合、クイック ソートの時間計算量は O(n^2) になります。平均すると、クイック ソートの時間計算量も O(nlogn) です。

クイック ソートの空間計算量は O(logn) です。ここで、logn は再帰呼び出しスタックの深さです。各パーティションが配列を正確に均等に分割する最良のケースでは、クイック ソートの空間複雑さは O(logn) です。最悪の場合、つまり各パーティションがピボット要素として配列の最小または最大の要素を見つける場合、クイック ソートの空間複雑さは O(n) です。平均すると、クイックソートのスペースの複雑さも O(logn) です。

クイック ソートのスペースの複雑さは、入力配列に加えて必要な追加スペースを指し、入力配列のスペースは含まれないことに注意してください。

要約すると、クイック ソートは、時間の計算量とスペースの計算量が少ない効率的な並べ替えアルゴリズムです。実際のアプリケーションでは、クイック ソートの最悪の場合の時間計算量は O(n^2) ですが、クイック ソートの平均時間計算量は O(nlogn) であり、実際のアプリケーションのデータは非常に小さいです。可能性は低いため、クイック ソートは依然として選択ソート アルゴリズムです。

以上がJava クイック ソート アルゴリズムの時間計算量と空間計算量を分析するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。