堆排序

堆排序

　　堆排序是基于选择排序的排序算法，相对于选择排序来说更加高级，效率也高，因为使用了基于完全二叉树的最大堆或者最小堆结构，想要输出结果是升序的就用最大堆，反之则用最小堆。最大堆就是完全二叉树中所有的非叶子节点的值都大于或者等于其孩子结点的值。所以利用这种结构，我们每一次都将最大堆堆顶元素（最大）和堆底元素做交换，然后将堆的大小减一，调整新堆的结构使其符合最大堆的定义，然后递归去交换堆顶元素和堆底元素的值即可，最后就能够得到已经排好序的数列。

java代码如下：

/**
 * 堆排序：构建最大堆，每次交换堆顶和堆尾元素
 * 关键在于：最大堆的构建
 * 最大堆的构建的关键在于：最大堆的元素调整
 * @author 1
 *
 */
public class HeapSort {
	public static void Heapsort(int [] arr) {
		if(arr==null || arr.length==1) {
			return;
		}
		buildMaxHeap(arr);
		for(int i=arr.length-1;i>=1;i--) {
			int temp=arr[0];
			arr[0]=arr[i];
			arr[i]=temp;
			maxHeapcon(arr,0,i);
		}
	}
	
	private static void buildMaxHeap(int [] arr) {
		if(arr==null || arr.length==1) {
			return;
		}
		//堆中最后一个不是叶子节点的结点就是arr.length/2
		for(int i=arr.length/2;i>=0;i--) {
			maxHeapcon(arr,i,arr.length);
		}
	}
	/**
	 * 调整最大堆
	 * @param arr 输入堆
	 * @param parent 当前的父节点位置
	 * @param hsize 堆的大小
	 */
	private static void maxHeapcon(int [] arr, int parent ,int hsize) {
		int left=parent*2+1;
		int right=parent*2+2;
		int largest=parent;
		
		if(left<hsize && arr[left]>arr[largest]) {
			largest=left;
		}
		
		if(right<hsize && arr[right]>arr[largest]) {
			largest=right;
		}
		
		if(largest!=parent) {
			int temp=arr[parent];
			arr[parent]=arr[largest];
			arr[largest]=temp;
			maxHeapcon(arr,largest,hsize);
		}
	}
	public static void main(String [] args) {
		int [] arr= {9,8,7,6,5,4,3,2,1};
		Heapsort(arr);
		for(int i:arr) {
			System.out.print(i+" ");
		}
	}
	
}

由上述代码可见，堆排序的时间复杂度为（nlogn）因为，交换的复杂度是n，而重建堆结构的复杂度是logn，而每次交换以后都要重建堆结构，所以是nlogn。空间复杂度为o(1)，因为只有一个temp值用来在交换时暂存值。