JAVA 알고리즘 시작 순서 정렬 실례

2222 단어 JAVA무더기 정렬
더미의 정렬을 배우려면 먼저 더미의 개념을 알아야 한다. 더미는 하나의 수조이다.완전 두 갈래 나무의 수조 저장 방식과 비슷하다.그러나 그와 다른 성질은 두 갈래 정렬 나무와 유사하다.최대 무더기와 최소 무더기의 구분이 있는데 최대 무더기는 루트 노드의 값이 모두 하위 노드의 값보다 크고 최소 무더기는 루트 노드의 값이 하위 노드의 값보다 작다는 것을 가리킨다.퇴적 정렬은 일반적으로 최대 퇴적을 사용하지만, 최소 퇴적은 우선 대기열을 구성할 수 있다.더미 안에 있는 방법은 더미의 성질을 유지하는 것이다. 즉, 우리 아래 코드의 maxheap 방법이다. 이것은 가장 큰 무더기의 성질을 유지하는 방법이다. 첫 번째 매개 변수는 더미, 즉 수조이다. 두 번째 매개 변수는 더미의 구체적인 노드 위치를 조정하는 것이다. 아마도 이 노드의 값이 가장 큰 무더기의 성질에 부합되지 않을 것이다. 그러면 이 가치가 있는 위치는 매개 변수로 하고size는 더미 안에 실제 저장된 유효한 원소 개수이다.아마도 수조의 길이는 더미 안에 실제 저장된 원소의 개수일 것이다. 그러나 반드시 모든 데이터가 우리가 최대 더미를 구축해야 하는 것은 아니다.알고리즘 도론에서 말한 좌자결점은 2xi이지만 우리 수조는 0부터 계산하기 때문에 좌자결점은 2xi+1이 된다.buildheap는 하나의 최대 무더기를 구축하는 것이다. 우리가 2분의 길이로 가는 이유는 이 점의 하위 노드는 모두 잎 노드이기 때문에 우리는 아래에서 위로 정렬을 해서 최대 무더기를 구축한다.우리의 퇴적 안의 모든 노드가 최대 퇴적 성질을 만족시킬 것을 보증했다.마지막 무더기 정렬은 첫 번째 노드를 꺼내서 나머지 노드를 다시 무더기 정렬하고 뿌리 노드를 꺼내는 것이다.이렇게 하면 우리가 매번 꺼낼 때마다 최대치를 보장한다.

public class HeapSort {
 private int getLeft(int i){
  return 2*i+1;
 }
 private int getRight(int i){
  return 2*i+2;
 }
 public void maxheap(int[] heap,int loc,int size){
  int l=getLeft(loc);
  int r=getRight(loc);
  int largest=loc;
  if(l<size&&heap[l]>heap[loc]){
   largest=l;
  }
  if (r<size&&heap[r]>heap[largest]) {
   largest=r;
  }
  if(largest!=loc){
   int cache=heap[loc];
   heap[loc]=heap[largest];
   heap[largest]=cache;
   maxheap(heap, largest, size);
  }
 }
 public void buildheap(int[] heap){
  for(int i=heap.length/2;i>=0;i--){
   maxheap(heap, i, heap.length);
  }
 }
 public void sort(int[] heap){
  buildheap(heap);
  for(int i=heap.length-1;i>1;i--){
   int cache=heap[0];
    heap[0]=heap[i];
    heap[i]=cache;
   maxheap(heap, 0,i );
  }
  int cache=heap[0];
   heap[0]=heap[1];
   heap[1]=cache;

 }

 public static void main(String[] args) {
  int[] heap=new int[]{4,1,5,3,7,12,65,7};
  HeapSort hs=new HeapSort();
  hs.sort(heap);
  for (int i = 0; i < heap.length; i++) {
   System.out.println(heap[i]);
  }
 }
}

좋은 웹페이지 즐겨찾기