자바의 힙 정렬이란 무엇입니까? 힙 정렬 소개

이 기사에서는 Java의 힙 정렬이 무엇인지 설명합니다. 힙 정렬 소개 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

• 힙 정렬 소개:
  힙 정렬은 두 단계로 나눌 수 있습니다. 힙 구성 단계에서는 원본 배열을 힙으로 재구성한 다음 싱킹 정렬 단계에서는 힙에서 모든 요소를 ​​순서대로 제거하고 정렬된 결과를 얻습니다.
  1. 힙 구성의 효과적인 방법은 오른쪽에서 왼쪽으로 싱크() 싱킹 함수를 사용하여 하위 힙을 구성하는 것입니다. 배열의 각 위치에는 하위 힙의 루트 노드가 있으며, 싱크()는 이러한 하위 힙에도 적용 가능합니다. 노드의 두 하위 노드가 이미 힙에 있는 경우 싱크() 메서드를 호출합니다. 노드는 이를 힙으로 결합할 수 있습니다. 크기 1의 하위 힙은 sing(), 즉 싱킹 작업이 필요하지 않으므로 건너뛸 수 있습니다. 싱킹 및 플로팅 작업에 대해서는 제가 작성한 우선순위 큐 기사를 참조하세요.
  2. 힙을 정렬하기 위해 첫 번째 단계를 통해 힙을 구성합니다. 이 힙에서 루트 노드는 항상 최대값을 갖는 노드이므로 루트 노드의 값을 배열의 마지막 값과 교환합니다. 그런 다음 싱크() 싱크를 사용하여 힙의 구조를 유지합니다.

• 특정 코드 구현:

public class PQSort{
	public static void main(String[] args){
		int[] a = {9,1,7,5,3,9,12,56,21,45};
		sort(a);
		for(int i=0;i<a.length system.out.print public int for>=0;k--){
				sink(a,k,N);
			}
			//通过不断把堆中最大值放到数组的后面来排序
			while(N>0){
				exch(a,0,N--);
				sink(a,0,N);
			}
	}
	//下沉函数
	private static void sink(int[] a, int i, int n){
		while(2*i+1a[j]) break;
			exch(a,i,j);
			i=j;
		}
	}
	//交换函数
	private static void exch(int[] a, int i, int j){
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}</a.length>

실행 결과:

위 내용은 자바의 힙 정렬이란 무엇입니까? 힙 정렬 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!