JAVA 정렬 힙 정렬

아래 편집기는 비교 정렬 및 힙 정렬에 대한 진부한 표현을 제공합니다. 에디터가 꽤 좋다고 생각해서 지금 공유해서 참고용으로 올려보겠습니다.

힙 정렬에는 완전한 이진 트리 지식이 필요합니다. 시퀀스를 {10, 2, 11, 8, 7}로 정렬하려면 아래 그림과 같이 완전한 이진 트리로 간주하세요.

힙은 큰 루트 힙과 작은 루트 힙으로 나뉩니다. 큰 루트 힙은 각 루트 노드가 하위 노드(L(i) >= L(2i) && L(i) > = L(2i + 1)), 작은 루트 힙은 각 루트 노드가 하위 노드(L(i)

이 기사에서는 대규모 루트 힙 구성을 예로 들어 설명합니다. .

힙 정렬의 첫 번째 단계 - 초기 힙 구축. 초기 힙을 구축하는 방법은 무엇입니까? 정의에 따르면 핵심 포인트는 각 루트 노드에 있습니다. 위에서 언급한 정렬 대상 시퀀스의 완전한 이진 트리를 관찰하면 노드 2와 노드 10에 주의가 필요한 노드인 자식 노드가 있음을 찾는 것은 어렵지 않습니다.

노드 2를 찾는 방법은 무엇인가요? 리프 노드, 즉 마지막 노드의 부모 노드임을 알 수 있는데, 완전 이진 트리의 속성에 따르면 루트 노드를 제외한 모든 노드의 부모 노드 수는 ⌊n/2⌋이다. n = 5라고 가정하면 노드 2의 개수가 ⌊5 / 2⌋ = ②라는 것을 쉽게 알 수 있습니다. 왼쪽과 오른쪽 자식 노드의 크기를 비교하여 조정합니다.

드디어 루트 노드 10이 남았습니다. 노드 2의 개수는 ②, ② - 1 = ①인 것으로 알려져 있는데, 이는 루트 노드 10의 개수를 얻게 된다는 의미입니다. 왼쪽과 오른쪽 자식 노드의 크기를 비교하여 조정합니다.

조정이 완료되면 "큰 루트 힙"이 형성된 것을 확인할 수 있습니다. 예제에서 정렬할 열은 비교적 간단하며, 관찰하기 위해 더 복잡한 정렬할 열을 제공합니다. 큰 루트 힙을 구축하는 과정입니다. {53, 17, 78, 09, 45, 65, 87, 32}로 정렬되는 시퀀스의 경우 이를 완전한 이진 트리로 처리합니다.

마찬가지로 주의해야 할 노드를 살펴보겠습니다.

첫 번째 예에 따르면 노드 09의 번호는 ⌊8 / 2⌋ = ④로, 노드 78의 번호는 ④ - 1 = ③... 등으로 쉽게 찾을 수 있습니다. 즉, 조정해야 할 노드 위치는 ⌊n / 2⌋부터 루트 노드 ①이 끝날 때까지 (⌊n / 2) 감소합니다. ⌋ ~ 1). 지금 조정을 시작하세요. ㅋㅋㅋ 추가 하향 조정이 필요합니다.

모든 상향 조정이 완료된 후 다시 돌아가서 하향 조정을 하는 것이 아니라 하향 조정이 필요한지 여부를 판단하기 위해 상향 조정을 할 때마다 하향 조정을 수행해야 합니다. 이런 식으로 큰 루트 힙이 설정되고 정렬할 열 배열의 상황이 {87, 45, 78, 32, 17, 65, 53, 09}로 변경되었습니다. 다음은 정렬 방법에 대한 질문입니다. 큰 루트 힙의 루트 노드를 마지막 노드와 교환하고 여전히 큰 루트 힙을 만족하도록 이진 트리를 조정합니다.

루트 노드와 마지막 노드를 호출한 후 정렬할 열의 최대값이 배열의 마지막 위치인 {..., 87}에 배치된 것을 확인할 수 있습니다. 이때 첫 번째 정렬은 다음과 같습니다. 완료되었으나 이 첫 번째 정렬은 아직 끝나지 않았습니다. 노드 87을 제외하고 다른 노드는 큰 루트 힙의 조건을 충족하지 않으므로 나머지 노드는 큰 루트 힙이 되도록 조정해야 합니다. 정렬 프로세스는 더 이상 제공되지 않습니다. Java 및 Python3의 코드 구현은 다음과 같습니다.

Java

package com.algorithm.sort.heap;

import java.util.Arrays;

/**
 * 堆排序
 * Created by yulinfeng on 6/20/17.
 */
public class Heap {
  
  public static void main(String[] args) {
    int[] nums = {53, 17, 78, 09, 45, 65, 87, 32};
    nums = heapSort(nums);
    System.out.println(Arrays.toString(nums));
  }
  
  /**
   * 堆排序
   * @param nums 待排序数组序列
   * @return 排好序的数组序列
   */
  private static int[] heapSort(int[] nums) {
  
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
      heapAdjust(nums, i, nums.length);
    }
    for (int i = nums.length - 1; i > 0; i--) {
      int temp = nums[i];
      nums[i] = nums[0];
      nums[0] = temp;
      heapAdjust(nums, 0, i);
    }
    return nums;
  }
  
  /**
   * 调整堆
   *
   * @param nums  待排序序列
   * @param parent   待调整根节点
   * @param length 数组序列长度
   */
  private static void heapAdjust(int[] nums, int parent, int length) {
    int temp = nums[parent];
    int childIndex = 2 * parent + 1;  //完全二叉树节点i从编号1开始的左子节点位置在2i，此处数组下标从0开始，即左子节点所在数组索引位置为：2i + 1
    while (childIndex < length) {
      if (childIndex + 1 < length && nums[childIndex] < nums[childIndex + 1]) {
        childIndex++;  //节点有右子节点，且右子节点大于左子节点，则选取右子节点
      }
      if (temp > nums[childIndex]) {
        break; //如果选中节点大于其子节点，直接返回
      }
      nums[parent] = nums[childIndex];
      parent = childIndex;
      childIndex = 2 * parent + 1;  //继续向下调整
    }
    nums[parent] = temp;
  }
}

Python3

#堆排序
def heap_sort(nums):

  for i in range(int(len(nums) / 2 - 1), -1, -1):
    heap_adjust(nums, i, len(nums))
  
  for i in range(len(nums) - 1, -1, -1):
    temp = nums[i]
    nums[i] = nums[0]
    nums[0] = temp
    heap_adjust(nums, 0, i)
  
  return nums

#调整堆
def heap_adjust(nums, parent, length):
  
  temp = nums[parent]
  childIndex = 2 * parent + 1
  while childIndex < length:
    if childIndex + 1 < length and nums[childIndex] < nums[childIndex + 1]:
      childIndex += 1
    if temp > nums[childIndex]:
      break
    nums[parent] = nums[childIndex]
    parent = childIndex
    childIndex = 2 * parent + 1
  
  nums[parent] = temp
    
nums = [53, 17, 78, 09, 45, 65, 87, 32]
nums = heap_sort(nums)
print(nums)

위의 진부한 비교정렬과 힙정렬은 모두 에디터가 공유해드린 내용이니 참고가 되셨으면 좋겠습니다. , 모두가 Script House를 지지해 주시길 바랍니다.

위 내용은 JAVA 정렬 힙 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!