Javaを使用してヒープソートアルゴリズムを実装する方法

Java を使用してヒープ ソート アルゴリズムを実装する方法

ヒープ ソートは、ヒープ データ構造に基づいたソート アルゴリズムであり、ヒープのプロパティを利用します。仕分け用に。ヒープ ソートは、ヒープの構築とソートという 2 つの主な手順に分かれています。

ヒープの構築:
まず、ソートする配列に基づいて、大きなルート ヒープまたは小さなルート ヒープを構築する必要があります。昇順ソートの場合は大きなルート ヒープを構築する必要があり、降順ソートの場合は小さなルート ヒープを構築する必要があります。

大きなルート ヒープの特性は、ノードの値がその子ノードの値以上であることです。
小さなルート ヒープのプロパティは次のとおりです。ノードの値はその子ノードの値以下です。

大規模なルート ヒープを構築するプロセスは次のとおりです:

public static void buildHeap(int[] array, int length) {
    for (int i = length / 2 - 1; i >= 0; i--) {
        heapify(array, length, i);
    }
}

public static void heapify(int[] array, int length, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < length && array[left] > array[largest]) {
        largest = left;
    }

    if (right < length && array[right] > array[largest]) {
        largest = right;
    }

    if (largest != i) {
        int temp = array[i];
        array[i] = array[largest];
        array[largest] = temp;
        heapify(array, length, largest);
    }
}

並べ替え:
大規模なルート ヒープを構築した後、ヒープの先頭の要素を最後の要素と交換する必要があります。配列の要素を削除し、ヒープ範囲を縮小してから、再度ヒープ化します。ヒープが空になるまでこのプロセスを繰り返します。最終的な配列は順序付けされます。

public static void heapSort(int[] array) {
    int length = array.length;

    buildHeap(array, length);

    for (int i = length - 1; i >= 0; i--) {
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;

        heapify(array, i, 0);
    }
}

使用例:

public static void main(String[] args) {
    int[] array = {4, 10, 3, 5, 1};
    heapSort(array);

    System.out.println(Arrays.toString(array));
}

出力結果は[1, 3, 4, 5, 10]で昇順の結果です。

ヒープ ソートの時間計算量は O(nlogn) です。ここで、n はソートされる要素の数です。ヒープ ソートは、大規模なデータのソートに適した安定したソート アルゴリズムです。

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