堆排序，是利用堆结构进行排序，一般是利用最大堆，即根节点比左右两个子树的节点都大，具体算法步骤如下。
一、创建堆
首先将数组中的元素调整成堆，对应下面程序中的createHeap（List<Integer> list）方法。创建堆就是从树中最后一个内节点（下标为（n-1）/2）开始调整数组中元素的位置，使以这个内节点为根的子树满足堆的结构。即依次将以(n-1)/2、(n-1)/2-1、(n-1)/2-2、…、1、0为根的子树调整为堆。
创建堆主要用了shiftDown操作，对应下面的shiftDown(List<Integer> list,int parent,int end)方法。该操作是不断将小元素下调的过程，如果根元素小于左右两个子树的较大者，那么根元素就要跟这个较大者进行交换，直到到达叶子节点为止。siftDown操作每下降一层要比较两次：1）选择左右子树的较大者，2）将较大者跟父亲比较。下降的最大高度即为父节点的高度。由结论：高度为h的满二叉树的所有节点的高度和为n-h-1，高度从0开始，叶子节点高度为0，此结论可由数学归纳法证明，可知最坏情况的比较次数约为2(n-h-1)，即创建堆的复杂度度为O(n)。
二、排序
当将数组调整成堆之后，由堆的定义可知，树的根就是最大的元素，这时我们可以将根删除，并将最后一个元素放到根的位置，然后将树重新调整为堆。重新调整为堆之后，根节点又为最大的元素，再删除，再调整，直到元素全部排序。（这里实际上是将最后一个元素和根元素交换，从此以后最后一个元素不在参与树的重新调整，即已经排好序的元素不再参与树的调整）。
shiftDown操作的时间复杂度为O(lgn)，即树的高度，排序过程中一共进行了n-1的shiftDown操作，所以可以粗略的推断出堆排序的时间复杂度为O(nlgn)。空间复杂度为O(1)。
三、优化
堆中从根节点到叶节点的一条路径是有序的，最大堆是降序，我们在shiftDown操作时，实际上是在找根节点在某条路径上的一个插入位置，可以借鉴二分的思想，我们可以一次下降到当前高度h的一半的位置（在下降的过程中要将沿途的较大的子节点上移，这样在h/2高度形成空位），即h/2，再比较在一半高度h/2的节点与根节点的大小，如果比根节点大则继续寻找当前一半高度位置的元素即h/4，依次类推，如果当前高度的元素比根节点小，我们就引入shiftUp操作，即将根节点再上移，，但由前面的分析可知，上移的次数是有限的，这样就将shiftDown的复杂度变为O(lglgn)，堆排序的总体复杂度变为O(n*lglgn)。
下面是堆排序的Java实现，未经优化，优化的代码以后有时间给出。
import java.util.Arrays;import java.util.List;/* *创建最大堆，并进行排序 */public class HeapSort {public void swap(List<Integer> list, int m,int n){int temp = list.get(n);list.set(n, list.get(m));list.set(m,temp);}public List<Integer> createHeap(List<Integer> list){ //创建堆，从第一个非孩子结点开始调整，创建一个最大堆int n = list.size();for(int k = (n-1)/2;k >= 0;k–){shiftDown(list,k,n-1);}return list;}//将以parent为根节点的二叉树调整为堆public void shiftDown(List<Integer> list,int parent,int end){boolean flag = true;while(parent*2+1<=end && flag){ //如果存在左孩子就进行调整int lChild = parent*2+1;int max=0;if(lChild+1<=end){ //表示存在右孩子int rChild = lChild+1;max = list.get(lChild)>list.get(rChild)?lChild:rChild;}else{max = lChild;}if(list.get(max)>list.get(parent)){ //有子孩子比父亲大swap(list,max,parent);parent = max;}else{flag = false;//表示孩子都比父亲要小，不需要调整了}}}public void sort(List<Integer> heap){ //排序主过程int n = heap.size();int rmd = n-1;while(rmd>0){swap(heap,0,rmd);shiftDown(heap,0,rmd-1);rmd–;}}public static void main(String[] args) { //测试算法HeapSort hs = new HeapSort();List<Integer> list = null;list = Arrays.asList(3,0,23,6,5,43,23,566,8,5,34,23,667,34,123);hs.createHeap(list);hs.sort(list);for(int i=0;i<list.size();i++){System.out.print(list.get(i)+" ");}}}
与那些新人和旧人们共同经历吧！
