排序算法之堆排序
java实现堆排序
快要考试了，复习了下排序算法，现对堆排序的实现过程作下详细记录。
概述
堆排序和插入排序一样，是一种原地排序算法；和归并排序一样，运行时间为O(nlgn)。二叉堆有两种，最大堆和最小堆，下面算法实现的是最大堆，即堆中最大元素存放在根节点。
算法实现
package Sort;
/**
* Created by carm on 2016/7/10.
* Heap.java
*/
public class Heap {
public static void sort(int []a){
int N = a.length;
/**
* build heap
* 完全二叉树使用数组结构存储，设数组大小为N，数组下标以0开始
* 因为叶节点可以看作是只含有一个元素的堆
* 故循环以非叶节点作为开始节点；
* 若数组大小为N，则 所有大于K =(N/2)-1的节点都是叶节点
*/
for(int k=N/2-1; k>=0; k--){
sink(a,k,N-1);
}
/**
* HeapSort
* 通过互换首末位置，将最大元素放到最终位置
*/
while(N>1){
swap(a,0,--N);
sink(a,0,N-1);
}
}
/**
*
* @param a
* @param k
* @param N 堆元素个数
*/
private static void sink(int []a, int k, int N){
/**
* MAX-HEAPIFY
* 数组下标以0开始，故左右孩子下标为2k+1与2k+2
*/
while(2*k+1 <= N){
int j= 2*k+1;
if(j<N && a[j]<a[j+1]) j++; //比较左右孩子节点，找最大值，下标记为j
if(a[k]>a[j]) break;
swap(a,k,j);
k = j;
}
}
private static void swap(int[] a, int j, int i) {
int t = a[j];
a[j]=a[i];
a[i]=t;
}
}
测试代码
package Sort;
/**
* Created by carm on 2016/7/10.
* test.java
*/
public class test {
public static void main(String []args){
int []a = {12,43,23,18,49,36,50,9,3};
Heap.sort(a);
for(int e: a){
System.out.print(" "+e);
}
}
}
运行结果
3 9 12 18 23 36 43 49 50
参考书籍
- 《算法导论》
- 《算法》第4版