Java를 사용하여 힙 정렬 알고리즘을 구현하는 방법

Java에서 힙 정렬 알고리즘을 구현하는 방법

힙 정렬은 힙의 특성을 활용하여 정렬하는 힙 데이터 구조 기반 정렬 알고리즘입니다. 힙 정렬은 힙 구축과 정렬이라는 두 가지 주요 단계로 나뉩니다.

힙 구축:
먼저 정렬할 배열을 기반으로 큰 루트 힙 또는 작은 루트 힙을 구축해야 합니다. 오름차순 정렬의 경우 큰 루트 힙을 구축해야 하며, 내림차순 정렬의 경우 작은 루트 힙을 구축해야 합니다.

큰 루트 힙의 속성은 다음과 같습니다. 노드의 값은 해당 하위 노드의 값보다 크거나 같습니다.
작은 루트 힙의 속성은 다음과 같습니다. 노드의 값은 해당 하위 노드의 값보다 작거나 같습니다.

큰 루트 힙을 만드는 과정은 다음과 같습니다:

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!