堆排序，顾名思义就是利用堆这个数据结构对数据项进行排序。前面提到过。堆数据结构中。节点大于或等于自己的子节点。那么我们能够将待排序的数据项依次加入到堆中，然后再依次取出根节点就可以。从堆中取出的数据项是从大到小排列的。由于根节点永远是最大的。而堆中永远是取根节点。假设对堆这样的数据结构不太了解的话，能够先看这篇博文：。这里不再赘述。

以下我们来看看堆排序的实现（假设程序有不清楚的地方。也能够參考上面那篇博文）。

public class HeapSort {	private int[] array;	private int currentIndex;	private int maxSize;	public HeapSort(int size) {		maxSize = size;		array = new int[maxSize];		currentIndex = 0;	}	//插入数据项，并排好序	public void insertSort(int[] source) {		for(int i = 0; i < source.length; i++) {			array[currentIndex] = source[i]; //插入到节点尾			tickedUp(currentIndex++); //向上又一次排好序。使得满足堆的条件		}	}	private void tickedUp(int index) {		int parentIndex = (index - 1) / 2; //父节点的索引		int temp = array[index]; //将新加的尾节点存在temp中		while(index > 0 && array[parentIndex] < temp) {			array[index] = array[parentIndex];			index = parentIndex;			parentIndex = (index - 1) / 2;		}		array[index] = temp;	}		//取出最大值	public int getMax() {		int maxNum = array[0];		array[0] = array[--currentIndex];		trickleDown(0);		return maxNum;	}	private void trickleDown(int index) {		int top = array[index];		int largeChildIndex;		while(index < currentIndex/2) { //while node has at least one child			int leftChildIndex = 2 * index + 1;			int rightChildIndex = leftChildIndex + 1;			//find larger child			if(rightChildIndex < currentIndex &&  //rightChild exists?					array[leftChildIndex] < array[rightChildIndex]) {				largeChildIndex = rightChildIndex;			}			else {				largeChildIndex = leftChildIndex;			}			if(top >= array[largeChildIndex]) {				break;			}			array[index] = array[largeChildIndex];			index = largeChildIndex;		}		array[index] = top;	}}

        算法分析：堆中插入和取出的时间复杂度均为O(logN)，所以堆排序算法的时间复杂度为O(NlogN)。可是堆排序也须要额外的和待排序序列大小同样的存储空间。空间复杂度为O(N)。

_____________________________________________________________________________________________________________________________________________________

-----乐于分享。共同进步！

-----很多其它文章请看：