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

堆排序分成两个过程

1、构建初始堆(构建初始堆后堆中元素并非有序，只是形成堆，如果是小顶堆的话，堆顶元素是最小的，同时左右子树也是堆。

我之前和那么TOP K 的问题混淆起来了，TOP K的问题是用K个元素建堆，那么堆排序是用多少个元素建堆呢?是用数组的全部元素建堆，然后把堆顶元素放到数组最后，完成一次排序过程，堆尾元素放到堆顶，进行调整。

package Sort;public class HeapSort {    /**     * 建堆函数，建堆函数中用到调整堆函数     * @param array     */    public static void buildHeap(int[] array){        for(int i = (array.length - 2)/2; i >= 0; i--){            adjustHeap(array,i,array.length - 1);        }    }    /**     * 调整堆函数,大根堆     * @param index 调整的树的根节点下标     * @param lastTreeIndex 这个是堆二叉树的最后一个节点的下标，因为我们每进行一次排序，实际上堆就少了一个节点     */    public static void adjustHeap(int[] array, int index,int lastTreeIndex){        //最后一个非叶子节点的下标是(lastTreeIndex - 1)/2;        while(index <= (lastTreeIndex - 1)/2){            int rightIndex = 2*index + 2;//右节点可能不存在            int leftIndex = 2*index + 1;            if(rightIndex > lastTreeIndex){                if(array[index] < array[leftIndex]){                  int tmp = array[index];                  array[index] = array[leftIndex];                  array[leftIndex] = tmp;                  index = leftIndex;                }else{                   break;                }            }else{                int maxValue = 0, maxIndex = 0;                if(array[leftIndex] > array[rightIndex]){                    maxValue = array[leftIndex];                    maxIndex = leftIndex;                }else{                    maxValue = array[rightIndex];                    maxIndex = rightIndex;                }                if(array[index] < maxValue){                    int tmp = array[index];                    array[index] = array[maxIndex];                    array[maxIndex] = tmp;                    index = maxIndex;                }else{                    break;                }            }        }    }    public static void heapSort(int[] array){        buildHeap(array);        for(int i = array.length - 1;i > 0; i--) {            int tmp = array[0];            array[0] = array[i];            array[i] = tmp;            if(i != 1) {                adjustHeap(array, 0, i - 1);//最后一次不能再调整堆了            }        }    }    public static void main(String[] args){        int[] array = {9,67,88,22323,23};        heapSort(array);        ArrayPrint.arrayPrint(array);    }}

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