堆排序(Heap Sort),java版

堆排序(Heap Sort),java版.

堆排序是高效的排序方法。没有最坏情况（即与平均情况一样），空间占用又小，综合效率比快速排序还好。

堆排序原理：1、从数据集中构建大顶堆（或小顶堆）。2、堆顶与最后一个数据交换，然后维护堆顶使它还是大顶堆（或小顶堆）。3、重复2的过程，直到剩下一个数据。
时间复杂度：平均O(nlog2n)，最坏情况O(nlog2n)。

示例代码：

1. package?com.chenlb.sort;??
2. ??
3. import?java.util.Arrays;??
4. ??
5. /**?
6. ?*?堆排序.?
7. ?*?
8. ?*?@author?chenlb?2008-12-28?下午03:52:53?
9. ?*/??
10. public?class?HeapSort?{??
11. ??
12. ????private?static?int?parentIdx(int?childIdx)?{??
13. ????????return?(childIdx?-?1)?/?2;??//索引从0开始,?注意childIdx=0时返回0??
14. ????}??
15. ??
16. ????private?static?int?leftChildIdx(int?parentIdx)?{??
17. ????????return?parentIdx*2?+?1;??
18. ????}??
19. ??
20. ????/**?
21. ?????*?构建大顶堆.?
22. ?????*?@author?chenlb?2008-12-28?下午03:52:23?
23. ?????*/??
24. ????private?static?void?buildMaxHeap(int[]?datas)?{??
25. ????????int?lastIdx?=?datas.length?-1;??
26. ????????for(int?i=parentIdx(lastIdx);?i>=0;?i--)?{??
27. ????????????int?k?=?i;??
28. ????????????/*boolean?isHeap?=?false;*/??
29. ????????????while(/*!isHeap?&&?*/leftChildIdx(k)?<=?lastIdx)?{??
30. ????????????????int?j?=?leftChildIdx(k);??
31. ????????????????if(j?<?lastIdx)?{????//有两个孩子??
32. ????????????????????if(datas[j]?<=?datas[j+1])?{?//j+1?比较大,?选择大的??
33. ????????????????????????j++;??
34. ????????????????????}??
35. ????????????????}??
36. ??
37. ????????????????if(datas[k]?>?datas[j])?{????//父的比较大??
38. ????????????????????/*isHeap?=?true;*/??
39. ????????????????????break;??
40. ????????????????}?else?{??
41. ????????????????????SortUtil.swap(datas,?k,?j);??
42. ????????????????????k?=?j;??
43. ????????????????}??
44. ????????????}??
45. ????????}??
46. ????}??
47. ??
48. ????/**?
49. ?????*?堆顶改变,?要维护大顶堆.?
50. ?????*?@author?chenlb?2008-12-28?下午03:53:04?
51. ?????*/??
52. ????private?static?void?maintainMaxHeap(int[]?datas,?int?lastIdx)?{??
53. ????????int?k?=?0;??
54. ????????while(k?<=?parentIdx(lastIdx))?{??
55. ????????????int?j?=?leftChildIdx(k);??
56. ????????????if(j?<?lastIdx)?{????//有两个孩子??
57. ????????????????if(datas[j]?<=?datas[j+1])?{?//j+1?比较大,?选择大的??
58. ????????????????????j++;??
59. ????????????????}??
60. ????????????}??
61. ????????????if(datas[k]?<?datas[j])?{????//父结点比较小??
62. ????????????????SortUtil.swap(datas,?k,?j);??
63. ????????????????k?=?j;??
64. ????????????}?else?{??
65. ????????????????break;??
66. ????????????}??
67. ????????}??
68. ????}??
69. ??
70. ????public?static?int[]?sort(int[]?datas)?{??
71. ????????buildMaxHeap(datas);??
72. ????????int?lastIdx?=?datas.length?-?1;??
73. ????????while(lastIdx?>?0)?{??
74. ????????????SortUtil.swap(datas,?0,?lastIdx);??
75. ????????????lastIdx--;??
76. ????????????if(lastIdx?>?0)?{??
77. ????????????????maintainMaxHeap(datas,?lastIdx);??
78. ????????????}??
79. ????????}??
80. ????????return?datas;??
81. ????}??
82. ??
83. ????public?static?void?main(String[]?args)?{??
84. ????????int[]?datas?=?{5,1,3,4,9,2,7,6,5};//{2,?9,?3,?7,?8,?6,?4,?5,?0,?1};??
85. ??
86. ????????/*buildMaxHeap(datas);?
87. ????????System.out.println(Arrays.toString(datas));*/??
88. ??
89. ????????sort(datas);??
90. ????????System.out.println(Arrays.toString(datas));??
91. ??
92. ????????datas?=?SortUtil.randomDates(10);??
93. ????????sort(datas);??
94. ????????System.out.println(Arrays.toString(datas));??
95. ??
96. ????}??
97. ??
98. }??

运行结果：

1. [1,?2,?3,?4,?5,?5,?6,?7,?9]??
2. [18,?185,?239,?304,?407,?489,?546,?688,?744,?821]??

待排序数据：5, 1, 3, 4, 9, 2, 7, 6, 5
构建大顶堆的过程：
5, 1, 3,?4, 9, 2, 7,?6, 5
5, 1,?3, 6, 9,?2,?7, 4, 5
5,?1, 7,?6,?9, 2, 3, 4, 5
5,?9, 7, 6, 1, 2, 3, 4, 5
9,?5, 7,?6, 1, 2, 3, 4, 5 -> 9, 6, 7, 5, 1, 2, 3, 4, 5

排序过程：
9, 6, 7, 5, 1, 2, 3, 4,?5
7, 6, 5, 5, 1, 2, 3,?4,?9
6, 5, 5, 4, 1, 2,?3,?7, 9
5, 5, 3, 4, 1,?2,?6, 7, 9
5, 4, 3, 2,?1,?5, 6, 7, 9
4, 2, 3,?1,?5, 5, 6, 7, 9
3, 2,?1,?4, 5, 5, 6, 7, 9
2,?1,?3, 4, 5, 5, 6, 7, 9
1,?2, 3, 4, 5, 5, 6, 7, 9

红色为交换。

?