本文共 1660 字，大约阅读时间需要 5 分钟。

堆排序原理就不解释了，大家可以自行查找，建议大家阅读《算法导论》第六章堆排序，很详细哦，在这里直接把源码贴出来。

如果大家想了解另外两种牛掰的排序算法，请猛戳下面链接

平均复杂度O(nlogn)

public class HeapSort {    public static int arr[] = {1,7,9,5,4,3,9,8,10,19,15,0,1};    //数组长度    public static int len = arr.length;    //堆中元素的有效元素 heapSize<=len    public static int heapSize = len;    public static void main(String[] args) {        heapSort();        print();    }    /**     * 堆排序     */    public static void heapSort(){        buildMaxHeap(); //构建大堆        for(int i = len-1;i>=1;i--){            int t = arr[i];            arr[i] = arr[0];            arr[0] = t;            heapSize--;            maxHeap(0);        }    }    /**     * 自底向上构建大堆     */    public static void buildMaxHeap(){        int size = len / 2;        for(int i = size;i>=0;i--){            maxHeap(i);        }    }    /**     * i节点为根及子树是一个大堆     * @param i     */    public static void maxHeap(int i){        int l = left(i);        int r = right(i);        int index = i;        if(l
   
    arr[index]){            index = l;        }        if(r
    
     arr[index]){            index = r;        }        if(index != i){            int t = arr[index];            arr[index] = arr[i];            arr[i] = t;            //递归向下构建堆            maxHeap(index);        }    }    /**     * 返回i节点的左孩子     * @param i     * @return     */    public static int left(int i){        return 2*i;    }    /**     * 返回i节点的右孩子     * @param i     * @return     */    public static int right(int i){        return 2*i+1;    }    /**     * 打印     */    public  static void print(){        for(int a:arr){            System.out.print(a+",");        }        System.out.println();    }
    
   

转载地址：http://gncrj.baihongyu.com/