Javaで実装された挿入ソートアルゴリズムの詳細説明

Java 挿入ソート アルゴリズムの実装方法の詳細説明

挿入ソートは、ソート対象のシーケンスを分割するという原理で、シンプルで直感的なソート アルゴリズムです。ソート済み部分とソートされていない部分。毎回、未ソート部分から 1 つの要素が取り出され、ソート済み部分の適切な位置に挿入されます。挿入ソートアルゴリズムの実装方法は比較的簡単ですが、具体的な実装方法と対応するコード例を以下に詳しく紹介します。

1. アルゴリズムのアイデア
   整数配列 arr を昇順にソートすると仮定します。最初は、arr[0] がソートされた部分とみなされ、残りの要素はソートされていない部分とみなされます。一部。これを踏まえて、現在挿入する要素が arr[i] (i は 1 から始まる) である場合、ソートされた部分 arr[0:i-1] から arr[i] を挿入する位置 j を見つけます。次に、arr[i] が位置 j に挿入され、arr[j:i-1] のすべての要素が順番に 1 つ後ろに移動されます。
2. コードの実装
   次は、Java 言語で挿入ソート アルゴリズムを実装するコード例です。

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;

            // 将已排序的元素依次向后移动，直到找到arr[i]应该插入的位置
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 3, 1};
        insertionSort(arr);
        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3. アルゴリズム分析
   挿入ソート アルゴリズムは O(n^2) です。ここで、n はソートされる要素の数です。最良の場合、つまりソート対象の配列がすでにソートされている場合、挿入ソートの時間計算量は O(n) です。最悪の場合、ソートされる配列は逆順になり、挿入ソートの時間計算量は O(n^2) になります。挿入ソートは、ソートの前後で等しい要素の相対位置が変わらないため、安定したソート アルゴリズムです。

要約すると、この記事では Java 挿入ソート アルゴリズムの実装方法を詳細に紹介し、対応するコード例を示します。挿入ソートは、小規模な配列または基本的に順序付けられた配列に適した、シンプルで直感的なソート アルゴリズムです。実際のアプリケーションでは、挿入ソートは他のより効率的なソート アルゴリズムに置き換えることができますが、挿入ソートの原理と実装方法を理解することは、他のソート アルゴリズムを学習するのに非常に有益です。

以上がJavaで実装された挿入ソートアルゴリズムの詳細説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。