Java 選択ソート アルゴリズムの実装とパフォーマンスの最適化手法

Java 選択ソート コードの完全な実装と最適化テクニック

Selection Sort は、シンプルで直感的なソート アルゴリズムです。その基本的な考え方は、un Sorts の最小 (または最大) 要素を配列内に取り込み、ソートされた配列の最後に配置します。配列全体が並べ替えられるまで、この手順を繰り返します。以下は、Java での選択ソートの完全な実装と最適化手法の詳細な説明です。

選択範囲の並べ替えの基本的な実装:

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

上記のコードでは、まず選択範囲の並べ替えのメイン メソッド selectionSort(int[] arr) を定義します。 main メソッドでは、最初に配列の長さを計算し、次に 2 つのネストされたループを通過して、ソートされていない部分の最小の要素を見つけ、それを現在の位置の要素と交換します。配列全体が並べ替えられるまで、この手順を繰り返します。最後に、main メソッドでサンプル配列を定義し、並べ替えのために selectionSort メソッドを呼び出します。

選択ソートの時間計算量は O(n^2) です。これは、要素の数が増加するにつれて、ソートに必要な時間が二次関数的に増加することを意味します。ただし、いくつかのテクニックを使用して、選択並べ替えの効率を向上させることができます。

最適化のヒント 1: 交換操作の数を減らす

選択ソートの各ラウンドで、ソートされていない部分の最小の要素を見つけて、それを現在の位置の要素と交換します。これは必要ですが、各スワップに 3 つの割り当てが必要な場合は、パフォーマンスに影響を与える可能性があります。最小要素のインデックス値を直接記録し、代入操作を 1 回だけ実行することで、交換の回数を減らすことができます。修正されたコードは次のようになります。

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

最適化のヒント 2: ソートされた部分をチェックする判定を追加します

各ラウンドで、ソートされていない部分を走査して最小の要素を見つけます。ただし、走査プロセス中に、ソートされた部分の最大の要素が未ソートの部分の最小の要素よりも小さいことが判明した場合、ソートは完了しており、ソート プロセスを早期に終了できます。修正されたコードは次のとおりです。

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            boolean sorted = true;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
                if (arr[j] < arr[j-1]) {
                    sorted = false;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
            if (sorted) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

上記の最適化手法により、選択ソートの実行効率を向上させることができます。

概要:

選択ソートはシンプルですが非効率なソート アルゴリズムです。交換操作の削減やソート部分の判定を追加することで、選択ソートの効率を向上させることができます。ただし、選択ソートの時間計算量は O(n^2) ですが、一部の特定のシナリオでは依然として効果的なソート アルゴリズムです。

この記事が、選択の並べ替えを理解して実装し、最適化手法を通じてアルゴリズムの効率を向上させるのに役立つことを願っています。

以上がJava 選択ソート アルゴリズムの実装とパフォーマンスの最適化手法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。