堆排序综合了插入排序和合并排序的优点。堆排序的运行时间为O（nlgn），并且是原地排序（像插入排序一样，在同一数组内排序）。
这里用到了一种堆数据结构，堆二叉树又叫二叉堆，分为两种：最大堆和最小堆。在最大堆中，最大堆特性是指除了根以外的每个节点
i，有
array[parent[i]] >= array[i];
最小堆相反。
建堆只需要一次，以后每次只需要维持根的最大堆性质就可以了，交换首尾值。
下面采用最大堆排序进行数组排序（也可以采用最小堆排序方法），用的的性质就是最大堆的根总是这个堆的最大值。
package com.chengmaoning.heapsort;public class HeapSort {// 维持最大堆性质。这里用了递归的方法，也可以采取循环的方式private void max_heapify(int[] nums, int start, int end) {int left = 2 * start + 1;int right = 2 * start + 2;int largest = start;if (left <= end && nums[left] > nums[start]) {largest = left;}if (right <= end && nums[right] > nums[largest]) {largest = right;}if (largest != start) {swap(nums, start, largest);max_heapify(nums, largest, end);}}/** * 堆排序 * * @param nums */private void heap_sort(int[] nums) {build_max_heap(nums); // 先建堆for (int i = 0; i < nums.length; i++) {int end = nums.length - 1 - i;swap(nums, 0, end); // 把找到的最大值与末尾值互换max_heapify(nums, 0, end - 1); // 以后每次维持以下标0的根的树为最大堆即可}}// 建堆private void build_max_heap(int[] nums) {// TODO Auto-generated method stubfor (int i = nums.length / 2; i >= 0; --i) {max_heapify(nums, i, nums.length - 1);}}/** * * @param nums * @param i * @param j */private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}/** * @param args */public static void main(String[] args) {// TODO Auto-generated method stubint[] nums = { 2, 40, 3, 9, 0, 3, 4, 5, 8, 34, 5, 3, 07, 9, 7, 2, 93,4, 8, 9, 3, 11, 4, 7 };HeapSort tester = new HeapSort();tester.heap_sort(nums);// tester.build_max_heap(nums);for (int i = 0; i < nums.length; i++) {System.out.print(nums[i] + " ");}}}
夫妇一条心，泥土变黄金。
