Java プログラミングで検索アルゴリズムと並べ替えアルゴリズムをすばやくマスターする方法

1. 検索アルゴリズム

バイナリ アルゴリズム

バイナリ サーチ (Binary Search) は、ハーフサーチとも呼ばれ、効率的な検索アルゴリズムです。その基本的な考え方は、順序付けされた配列 (またはセット) を 2 つに分割することです。現在の中央の要素がターゲット要素と等しい場合、検索は成功します。現在の中央の要素がターゲット要素より大きい場合、左半分が検索されます。 ; 現在の中央の要素がターゲット要素より小さい場合、右半分を検索します。目的の要素が見つかるか、検索範囲が空になって検索が失敗するまで、上記の手順を繰り返します。

次は、Java で実装されたバイナリ アルゴリズムです。

public static int binarySearch(int[] arr, int target) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

上記のメソッドは、順序付けられた整数配列のセットとターゲット値をパラメーターとして使用し、ターゲット値のインデックスを返します。 array; if 対象の値が配列内に存在しない場合は、-1 が返されます。

アルゴリズムの中核は while ループで、左右が特定の条件を満たしたときに繰り返し実行されます。

• mid が target と等しい場合、mid が返されます。そしてアルゴリズムは終了します ;

• mid がターゲットより大きい場合は、左側で検索を続けます、つまり、右側を Mid - 1 に設定します;

• mid がターゲットより小さい場合は、右側で検索を続けます。つまり、左側を Mid 1 に設定します。

ループを実行するたびに、mid = left (right - left) / 2 を使用して中央要素のインデックスを計算します。 (left right) / 2 の形式ではなく、left right の形式を使用する必要があることに注意してください。そうしないと、整数オーバーフローの問題が発生する可能性があります。

2. 並べ替えアルゴリズム

Java では、並べ替えアルゴリズムは Comparable または Comparator インターフェイスを実装することによって実装されます。以下に、一般的に使用されるいくつかの並べ替えアルゴリズムとその実装方法を示します。

バブル ソート

バブル ソートは、単純な並べ替えアルゴリズムです。アイデアは、2 つの隣接する要素を常に比較し、順序が間違っている場合は位置を交換することです。この過程は水の泡が立ち上るのに似ているので、バブルソーティングと呼ばれます。

public static void bubbleSort(int[] arr) {
    int temp;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                //交换位置
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

選択ソート

選択ソートの考え方は、未ソートの要素から最小の要素を選択し、ソートの最後に置くことです。最小の要素が見つかるたびに、その位置が現在ソートされていない最初の要素と交換されます。

public static void selectionSort(int[] arr) {
    int minIndex;
    for (int i = 0; i < arr.length - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        //交换位置
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

挿入ソート

挿入ソートの考え方は、ソートされていない要素をソートされた適切な位置に挿入することです。未ソートの要素から要素を選択し、ソート済みの要素を後ろから前に移動します。ソート済みの要素より小さい場合は、1 つ後ろに移動して比較を続け、未ソートの要素より小さい位置が見つかるまで、その要素を次の位置に挿入します。この場所。

public 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;
    }
}

クイック ソート

クイック ソートは、分割統治の考え方に基づいた並べ替えアルゴリズムです。ピボット ポイントを選択し、配列をピボット ポイント以下とピボット ポイントより大きい 2 つの部分配列に分割し、2 つの部分配列を再帰的に並べ替えます。

rree

以上がJava プログラミングで検索アルゴリズムと並べ替えアルゴリズムをすばやくマスターする方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。