Javaで挿入ソートアルゴリズムを実装するにはどうすればよいですか?

1. 基本的な考え方

挿入ソート (Insertion-Sort) のアルゴリズムの説明は、シンプルで直感的なソート アルゴリズムです。これは、順序付けされたシーケンスを構築することで機能し、並べ替えられていないデータの場合は、並べ替えられたシーケンス内で後ろから前にスキャンし、対応する位置を見つけて挿入します。

2. アルゴリズム分析

1. アルゴリズムの説明

一般的に、挿入ソートは配列に対して in-place を使用して実装されます。具体的なアルゴリズムは次のように説明されます:

• 最初の要素から開始して、要素はソートされていると見なされます;

• 取り出し次の要素、並べ替えられた要素シーケンスを後ろから前にスキャンします;

• 要素 (並べ替えられた) が新しい要素より大きい場合、要素を次の位置に移動します;

• 並べ替えられた要素が新しい要素以下になる位置が見つかるまで手順 3 を繰り返します。

• その位置に新しい要素を挿入します。位置;

• 手順 2 ～ 5 を繰り返します。

#2. プロセス分析

(1) 最初の要素 (1) を並べ替え済みとしてマークします。

(2)、ソートされていない最初の要素 (28) を抽出します。

(3) 抽出した要素が挿入されている場所を見つけ、ソートされた要素 1 と比較します。

(4)、1 > 28 が true (False) でない場合は、既存の位置に要素を挿入します。

(5). 抽出した要素が挿入されている場所を見つけ、ソートされた要素と比較します28。

(6), 28 > 3 true (True) の場合、現在ソートされている要素 ({val1}) が 1 スペース右に移動されます。

(7) 抽出した要素が挿入されている場所を見つけ、ソートされた要素 1 と比較します。

(8)、1 > 3 が true (False) でない場合は、既存の位置に要素を挿入します。

(9) など

#3. アルゴリズムの実装

package com.algorithm.tenSortingAlgorithm;

import java.util.Arrays;

public class InsertionSort {
    private static void insertionSort(int[] arr) {
        int preIndex, current;
        for (int i = 1; i < arr.length; i++) {
            preIndex = i - 1;
            current = arr[i];
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,28,3,21,11,7,6,18};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

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