堆排序分析及优化

堆排序，是利用堆结构进行排序，一般是利用最大堆，即根节点比左右两个子树的节点都大，具体算法步骤如下。

一、创建堆

        首先将数组中的元素调整成堆，对应下面程序中的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)+" ");
		}
	}
}