Java で挿入ソート アルゴリズムを記述する方法と原則

挿入ソート アルゴリズムの手順と考え方

挿入ソートは、シンプルで直感的なソート アルゴリズムです。その基本的な考え方は、ソートする要素をシーケンス内の適切な位置にソートされます。

具体的な手順は次のとおりです。

1. まず、配列を 2 つの部分 (並べ替えられた部分と並べ替えられていない部分) に分割します。最初は、並べ替えられた部分には要素が 1 つだけあり、それが配列の最初の要素になります。
2. 未ソート部分から要素を順番に取り出し、ソート済み部分の要素と1つずつ比較し、適切な位置を見つけて挿入します。
3. 比較プロセス中に、並べ替えられた部分の要素を後方に移動して、挿入された要素のためのスペースを確保します。
4. 最後に、未ソート部分のすべての要素をソート済み部分の適切な位置に挿入すると、ソートが完了します。

次は、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;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

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

    public static void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

このコード例では、insertionSort メソッドを定義します。 accepts 整数の配列が引数として取られ、その配列がソートされて挿入されます。 n を使用して配列の長さを表し、for を使用して未ソート部分の要素をループします。各トラバーサルでは、現在の要素 arr[i] を key 変数に保存し、ソートされた部分を前方にトラバースして、key# # を挿入する適切な位置を見つけます。 ＃。比較プロセス中に、key 用のスペースを確保するために、大きい要素を 1 つ後ろの位置に移動します。最後に、key を正しい位置に挿入すると、並べ替えが完了します。

main メソッドでは、整数配列 arr を初期化し、insertionSort メソッドを呼び出して配列を並べ替えます。最後に、printArray メソッドを呼び出して、並べ替えられた配列を出力します。

上記のコードを実行すると、次の出力が得られます。

原数组：
5 2 8 1 9 3 
排序后的数组：
1 2 3 5 8 9 

挿入ソート アルゴリズムの時間計算量は O(n^2) です。ここで、n は配列の長さです。 。挿入ソート アルゴリズムは時間の複雑さは高くなりますが、その実装は単純であり、小規模な配列のソートに適しています。同時に、実際のアプリケーションでは、挿入ソートアルゴリズムは安定性という特徴もあります。

以上がJava で挿入ソート アルゴリズムを記述する方法と原則の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。