Javaクイックソート機能の効率を向上させるための戦略とテクニック

Java クイック ソート関数を最適化するための方法とテクニック

Quicksort (クイックソート) は、一般的なソート アルゴリズムです。そのアイデアは、配列をより小さなものに分割することです。並べ替えを行うには 2 つの大きなサブ配列を使用し、全体的な順序付けを行うにはサブ配列を再度並べ替えます。実際のアプリケーションでは、ソートの効率を向上させるために、クイックソート機能のパフォーマンスを最適化する必要があります。以下では、クイックソート機能を最適化するためのいくつかの方法とテクニックを紹介し、具体的なコード例を示します。

1. 参照要素のランダムな選択
   クイック ソートでの参照要素の選択は、ソートの効率に重要な影響を与えます。従来のアプローチでは、最初または最後の要素をベース要素として選択します。ただし、配列がすでにソートされているか、ほぼソートされている場合、この選択方法によりクイックソートの時間計算量が O(n^2) に低下する可能性があります。この状況を回避するには、要素を参照要素としてランダムに選択します。これにより、入力データの順序がある程度崩れ、パフォーマンスが向上します。

以下は、参照要素をランダムに選択するコード例です:

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = randomPartition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    public static int randomPartition(int[] arr, int low, int high) {
        int randomIndex = ThreadLocalRandom.current().nextInt(low, high + 1);
        swap(arr, randomIndex, high);
        return partition(arr, low, 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 = {5, 9, 1, 3, 7, 6};
        quickSort(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));
    }
}

2. 3 つのサンプリング パーティション
   従来のクイック ソート アルゴリズムでは、単一の参照要素が使用されます。配列を分割します。ただし、配列内に重複する要素が多数ある場合、このような分割によりクイック ソートの時間計算量は O(n^2) に低下します。この問題を解決するには、Median-Of-Three 分割法を使用して、参照要素の選択をより柔軟に行うことができます。

3 サンプリング除算の基本的な考え方は、配列内の 3 つの要素 (最初、最後、中間の要素など) を選択し、それらの中央値を参照要素として使用することです。このような分割方法を使用することで、多数の繰り返し要素を処理する場合のクイック ソートによるパフォーマンスの低下の問題を回避することができます。

次は、3 サンプリング パーティショニングを使用したコード例です。

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int[] pivotIndices = medianOfThree(arr, low, high);
            int left = pivotIndices[0];
            int right = pivotIndices[1];
            quickSort(arr, low, left - 1);
            quickSort(arr, left + 1, right - 1);
            quickSort(arr, right + 1, high);
        }
    }

    public static int[] medianOfThree(int[] arr, int low, int high) {
        int mid = (low + high) / 2;
        if (arr[high] < arr[low]) {
            swap(arr, low, high);
        }
        if (arr[mid] < arr[low]) {
            swap(arr, low, mid);
        }
        if (arr[high] < arr[mid]) {
            swap(arr, mid, high);
        }
        swap(arr, mid, high - 1);
        return partition(arr, low + 1, high - 1);
    }

    public static int[] partition(int[] arr, int low, int high) {
        int left = low;
        int right = high;
        int pivot = arr[high];
        int i = low - 1;
        while (true) {
            while (arr[++i] < pivot) {
            }
            while (left < right && pivot < arr[--right]) {
            }
            if (left >= right) {
                break;
            }
            swap(arr, left, right);
        }
        swap(arr, left, high);
        return new int[]{left, right};
    }

    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 = {5, 9, 1, 3, 7, 6};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

基本要素をランダムに選択し、3 サンプリング パーティショニングを使用することにより、Java クイック ソート関数のパフォーマンスを最適化できます。これらの方法により、さまざまなデータ分布を処理する際の並べ替えアルゴリズムの効率が向上し、時間の複雑さの低下を回避できます。

以上がJavaクイックソート機能の効率を向上させるための戦略とテクニックの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。