堆排序其实最主要的两个过程：第一步，创建初始堆；第二步，交换根节点与最后一个非叶子节
第一步实现 ：从最后一个非叶子节点为开始向前循环每个会支节点，比较每个分支节点与他左右子节点，如果其中某个子节点比父节点大，则与父节点交换，交换后原父节点可能还小于原子节点的子节点，所以还需对原父节点进行调整，使用原父节点继续下沉，直到没有子节点或比左右子节点都大为止，调用过程可通过递归完成。当某个非叶子节点调整完毕后，再处理下一个非叶子节点，直到根节点也调整完成，这里初始堆就创建好了，这里我们创建的是大顶堆，即大的元素向树的根浮，这样排序最后得到的结果为升序，因为最大的从树中去掉，并从数组最后往前存放。
第二步实现 ：将树中的最后一个元素与堆顶元素进行交换，并从树中去掉最后叶子节点。交换后再按创建初始堆的算法调整根节点，如此下去直到树中只有一个节点为止。
Java代码
1. package sort; 2.
3. import java.util.Comparator; 4.
5. public class HeapSort> extends Sort { 6. 7. /**
8. * 排序算法的实现，对数组中指定的元素进行排序 9. * @param array 待排序的数组 10. * @param from 从哪里开始排序 11. * @param end 排到哪里 12. * @param c 比较器 13. */
14. public void sort(E[] array, int from, int end, Comparator c) { 15. //创建初始堆
16. initialHeap(array, from, end, c); 17. 18. /*
19. * 对初始堆进行循环，且从最后一个节点开始，直接树只有两个节
点止
20. * 每轮循环后丢弃最后一个叶子节点，再看作一个新的树 21. */
22. for (int i = end - from + 1; i >= 2; i--) {
23. //根节点与最后一个叶子节点交换位置，即数组中的第一个元素与最后一
个元素互换
24. swap(array, from, i - 1); 25. //交换后需要重新调整堆
26. adjustNote(array, 1, i - 1, c); 27. } 28. 29. } 30. 31. /**
32. * 初始化堆
33. * 比如原序列为：7,2,4,3,12,1,9,6,8,5,10,11 34. * 则初始堆为：1,2,4,3,5,7,9,6,8,12,10,11 35. * @param arr 排序数组 36. * @param from 从哪 37. * @param end 到哪 38. * @param c 比较器 39. */
40. private void initialHeap(E[] arr, int from, int end, Comparator c) { 41. int lastBranchIndex = (end - from + 1) / 2;//最后一个非叶子节点 42. //对所有的非叶子节点进行循环 ，且从最一个非叶子节点开始 43. for (int i = lastBranchIndex; i >= 1; i--) { 44. adjustNote(arr, i, end - from + 1, c); 45. } 46. } 47. 48. /**
49. * 调整节点顺序，从父、左右子节点三个节点中选择一个最大节点与
父节点转换
50. * @param arr 待排序数组
51. * @param parentNodeIndex 要调整的节点，与它的子节点一起进行
调整
52. * @param len 树的节点数 53. * @param c 比较器 54. */
55. private void adjustNote(E[] arr, int parentNodeIndex, int len,
Comparator c) {
56. int minNodeIndex = parentNodeIndex; 57. //如果有左子树，i * 2为左子节点索引 58. if (parentNodeIndex * 2 <= len) { 59. //如果父节点小于左子树时
60. if (c.compare(arr[parentNodeIndex - 1], arr[parentNodeIndex * 2 - 1]) <
0) {
61. minNodeIndex = parentNodeIndex * 2;//记录最大索引为左子
节点索引
62. }
63.
64. // 只有在有或子树的前提下才可能有右子树，再进一步断判是否有右子树 65. if (parentNodeIndex * 2 + 1 <= len) { 66. //如果右子树比最大节点更大
67. if (c.compare(arr[minNodeIndex - 1], arr[(parentNodeIndex * 2 + 1) - 1])
< 0) {
68. minNodeIndex = parentNodeIndex * 2 + 1;//记录最大索引
为右子节点索引
69. } 70. } 71. } 72.
73. //如果在父节点、左、右子节点三都中，最大节点不是父节点时需交换，
把最大的与父节点交换，创建大顶堆
74. if (minNodeIndex != parentNodeIndex) {
75. swap(arr, parentNodeIndex - 1, minNodeIndex - 1); 76. //交换后可能需要重建堆，原父节点可能需要继续下沉
77. if (minNodeIndex * 2 <= len) {//是否有子节点，注，只需判断是否有左子
树即可知道
78. adjustNote(arr, minNodeIndex, len, c); 79. } 80. } 81. } 82. 83. /** 84. * 测试
85. * @param args 86. */
87. public static void main(String[] args) {
88. Integer[] intgArr = { 7, 2, 4, 3, 12, 1, 9, 6, 8, 5, 10, 11 }; 89. HeapSort sort = new HeapSort(); 90. HeapSort.testSort(sort, intgArr); 91. HeapSort.testSort(sort, null); 92. } 93. }