java 堆排序的实现

浏览数：15 / 时间：2015年06月08日

堆就是一个完全二叉树，堆要求是指该节点大于它的两个子节点。而两个字节点大小不一定。

堆排序的最坏时间复杂度为nlog(n)，平均也为nlog(n)，占用空间为o(1)，是一种比较排序算法。

堆排序也可以用于找最大的k个数。时间复杂度为klog(n)，因为建堆后，每次循环实际上都生成一个最大数。

下面见代码：

//从小到大排序
public class HeapSort {
    private int[] A;
    private int heapSize;
    //构造函数，传入待排序数组
    public HeapSort(int[] A){
        this.A = A;
    }
    public int[] getSortedArray(){
        return A;
    }
    
    //从节点i出发，使得父节点的数不小于子节点的数
    private void heapify(int i) {
        //加1、加2后才是该节点的两个子节点
        int left = 2*i + 1;
        int right = 2*i + 2;
        int largest = 0;
        
        //取得该节点、两个子节点中最大的编号
        if (left < heapSize &&  A[left] > A[i]) {
            largest = left;
        }else {
            largest = i;
        }
        
        if (right < heapSize && A[right] > A[largest]) {
            largest = right;
        }
        //若最大编号不是它，则继续建堆，否则就满足堆要求
        if (largest != i) {
            int temp = A[i];
            A[i] = A[largest];
            A[largest] = temp;
            heapify(largest);
        }
    }
    
    private void buildHeap(){
        heapSize = A.length;
        for (int i = (heapSize/2 - 1); i >= 0; i--) {
            heapify(i);
        }
    }
    
    private void heapSort(){
        buildHeap();
        int temp;
        for (int i = A.length-1; i > 0; i--) {
            temp = A[i];
            A[i] = A[0];
            A[0] = temp;
            heapSize--;
            heapify(0);
        }
    }
    
    public static void main(String[] args) {
//测试用例
        int[] array = {16,4,10,14,7,9,3,2,8,1,5,3,6,100};
        HeapSort heapSort = new HeapSort(array);
        heapSort.heapSort();
        for (int i : heapSort.A) {
            System.out.println(i);
        }
    }
}