堆排序

堆排序

分为两部分来说：一是堆的实现、二是堆的排序

堆的实现：

public class MaxPQ{ private int[] pq; private int N = 0; public MaxPQ(int maxN){ pq = new int[maxN+1]; } public boolean isEmpty(){ return N==0; } public boolean size(){ return N; } public void insert(int v){ pq[++N] = v; swim(pq,1,N); } public int delMax(){ int max = pq[1]; //从根节点得到最大元素 swap(pq,1,N--); //将其和最后一个节点交换 pq[N+1] = null; //防止对象游离 sink(pq,1,N); //恢复堆的有序性 return max; } private void swap(int[] a,int i,int j){ int temp = a[i]; a[i] = a[j]; a[j] = temp; } //某个节点变得比父节点更大而打破，我们需要交换它和它的父节点來修复堆 private void swim(int[] pq,int lo,int hi){ while(hi>lo&&pq[hi/2]<pq[hi]){//比父节点大，进行调整 swap(pq,hi/2,hi); hi = hi/2; } } //某个节点比它的两个或一个子节点小，需要交换它和它的子节点来修复堆 private void sink(int[] pq,int lo,int hi){ while(lo*2<=hi){ int j = 2*lo; if(j<hi&&pq[j]<pq[j+1]) j++;//找到子元素中最大的那个 if(pq[lo]>pq[j]) break; swap(pq,lo,j); lo = j; } } }

2、堆排序

堆排序分为堆构造和下沉排序两个阶段。

堆构造阶段将原始数组重新组织安排进一个堆中；下沉排序阶段，我们从堆中按递减顺序取出所有元素并得到排序结果（将堆中的最大元素删除，然后放进堆缩小后数组中空出的位置）。

public void sort(int[] a){ int N = a.length; for(int i=N/2;i>=1;i--){//构造堆 sink(a,i,N); //sink构造子堆 } while(N>1){ sort(a,1,N--); //将堆中最大元素删除，然后放进堆缩小后数组中空出来的位置 sink(a,1,N); // } }