基本思想：
图示： （88,85,83,73,72,60,57,48,42,6）
平均时间复杂度：
O(NlogN)由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N * logN)。
Java代码实现：
public class HeapSortTest {public static void main(String[] args) {// TODO Auto-generated method stubint[] arr = new int[] { 10, 3, 2, 5, 6, 1, -2, 3, 14, 12, 3, 8, 55, 44,-10 };print(arr);heapSort(arr);System.out.println("排序后的数组：");print(arr);}private static void print(int[] a) {for (int i = 0; i < a.length; i++) {System.out.print(a[i] + "\t");}System.out.println();}private static void swap(int[] a, int i, int j) {a[i] = a[i] + a[j];a[j] = a[i] - a[j];a[i] = a[i] - a[j];}private static void heapSort(int[] a) {for (int i = a.length - 1; i >= 0; i--) {createMaxHeap(a, i);swap(a, 0, i);print(a);}}private static void createMaxHeap(int[] a, int lastIndex) {for (int i = (lastIndex - 1) / 2; i >= 0; i--) {int k = i;while ((2 * k + 1) <= lastIndex) {int biggerIndex = 2 * k + 1;if (biggerIndex < lastIndex) {if (a[biggerIndex] < a[biggerIndex + 1]) {biggerIndex++;}}if (a[k] < a[biggerIndex]) {swap(a, k, biggerIndex);k = biggerIndex;} else {break;}}}} }
