最近开始学习排序的相关知识，计划以后每天都要整理一个排序的算法。

    今天整理了堆排序的排序算法，起初自己并不了解堆排序的相关过程，在阅读了博客http://www.cnblogs.com/luchen927/archive/2012/03/08/2381446.html之后，才对这方面的知识有所了解，在看了此博客的指导之后，感觉他写的代码有点问题，所以就自己重新写了一个。

其中最需要注意的就是：

根据根结点i（i为数组中的下标）来计算其左右孩子的坐标时，left = i * 2 + 1, right = i * 2 + 2， 因为根节点是从数组0位置开始的。

import java.util.Arrays;/** * 堆排序的介绍： * 堆排序对于记录数较少的文件并不提倡，但对n较大的文件还是很有效的。 * 其最坏情况下的时间复杂度为：O(nlogn)， 在最好情况下，时间复杂度为：O(1). * 堆排序是不稳定的排序。 *  *  *  *堆排序的具体过程： * 1 、首先从第一个非叶子节点开始，比较当前节点和其孩子节点，将最大的元素放在当前节点，交换当前节点和最大节点元素。 * 2 、将当前元素前面所有的元素都进行1的过程，这样就生成了最大堆 * 3 、将堆顶元素和最后一个元素交换，列表长度减1。由此无序区减1，有序区加1 * 4 、剩余元素重新调整建堆 * 5 、 继续3和4，直到所有元素都完成排序 * * **/public class HeapSort{		public static void heapSort(int[] num){		if(num == null) return;				int len = num.length;				buildHeap(num, len);				/**每次将堆顶元素放到数组最后的位置*/		while(len > 1){			swap(num, len - 1, 0);			len --;			adjustHeap(num, len, 0);		}	}		/**将一个无序的数组构建成一个大顶堆*/	private static void buildHeap(int[] num, int len) {				/**begin为最后一个根节点在数组中的下标*/		int begin = len / 2 -1;				/**依次遍历每一个根节点，通过调整，使每一个根节点都比它的孩子结点大*/		for(int i = begin; i >= 0; i--){			adjustHeap(num, len, i);		}	}	/**调整根节点和孩子结点的位置，使其满足大顶堆*/	private static void adjustHeap(int[] num, int len, int i) {		/**获取下标为i的根节点的左孩子和右孩子在数组中的下标*/		int leftChild = i * 2 + 1;		int rightChild = i * 2 + 2;				/**将本次调整的最大值下标暂时记为i*/		int max = i;				while(leftChild < len || rightChild < len){			/**如果num[max]的左孩子num[leftChild]比max大,将leftChild暂存在max中*/			if(leftChild < len && num[max] < num[leftChild]){				max = leftChild;			}						/**如果num[max]的右孩子num[rightChild]比max大,将rightChild暂存在max中*/			if(rightChild < len && num[max] < num[rightChild]){				max = rightChild;			}						/**如果在前面的运算中，发生过赋值*/			if(i != max){				swap(num, max, i);								i = max;				leftChild = i * 2 + 1;				rightChild = i * 2 + 2;			}else{				break;			}		}//while(leftChild < len || rightChild < len)	}//private static void adjustHeap()	/**将数组中num[x]和num[y]位置交换*/	private static void swap(int[] num, int x, int y) {		num[x] = num[x] ^ num[y];		num[y] = num[x] ^ num[y];		num[x] = num[x] ^ num[y];			}			public static void main(String[] args) {		int[] num = {0, 9, 7, 0, 0, 6, -40, 200};		HeapSort.heapSort(num);		System.out.println(Arrays.toString(num));			}}