堆排序，顾名思义就是利用堆这个数据结构对数据项进行排序，前面提到过，堆数据结构中，节点大于或等于自己的子节点。那么我们可以将待排序的数据项依次添加到堆中，然后再依次取出根节点即可。从堆中取出的数据项是从大到小排列的。因为根节点永远是最大的，而堆中永远是取根节点。如果对堆这种数据结构不太了解的话，可以先看这篇博文：数据结构和算法之 堆，这里不再赘述。
下面我们来看看堆排序的实现（如果程序有不清楚的地方，也可以参考上面那篇博文）。
- 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];
- 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) {
- int leftChildIndex = 2 * index + 1;
- int rightChildIndex = leftChildIndex + 1;
-
- if(rightChildIndex < currentIndex &&
- 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)。
转载：http://blog.csdn.net/eson_15/article/details/51193399
