有意思的排序算法堆排序
堆排序，是一个非常优秀的排序算法，像合并排序而不像插入排序，其运行时间为O(nlgn)，像插入排序而不像合并排序，它是一种原地排序算法，所以说，堆排序将插入排序和合并排序的优点结合起来了。
堆排序借助于堆数据结构，（二叉）堆是一个数组，它可以被视为一棵完全二叉树，树中每个节点与数组中存放该节点值得那个元素对应。
堆排序算法可以分为以下几步：
1） 建立原先数列对应的最大（或最小）堆。
2） 重复n-1次循环，每次选出一个最大（或最小）值，并放到合适的位置。
Java代码实现如下：
1 public class HeapSort implements SortAlgorithm {
2
3 private IntArray A = null ;
4
5 public HeapSort() {
6 A = new IntArray();
7 }
8
9 private class IntArray {
10 public int [] aArray = null ;
11 public int heapSize = 0 ;
12 }
13
14 @Override
15 public void sort( int [] A) {
16 maxHeapSort(A);
17 }
18
19 @Override
20 public void sort( int [] A, boolean isInc) {
21 if (isInc) {
22 maxHeapSort(A);
23 } else {
24 minHeapSort(A);
25 }
26 }
27
28 /**
29 * 最大堆排序，升序
30 *
31 * @param A
32 * int数组
33 */
34 private void maxHeapSort( int [] A) {
35 this .A.aArray = A;
36 this .A.heapSize = A.length;
37 buildMaxHeap( this .A);
38 for ( int i = A.length; i >= 2; i-- ) {
39 exchange(1 , i);
40 this .A.heapSize = this .A.heapSize - 1 ;
41 maxHeapify( this .A, 1 );
42 }
43 }
44
45 /**
46 * 最小堆排序，降序
47 *
48 * @param A
49 * int数组
50 */
51 private void minHeapSort( int [] A) {
52 this .A.aArray = A;
53 this .A.heapSize = A.length;
54 buildMinHeap( this .A);
55 for ( int i = A.length; i >= 2; i-- ) {
56 exchange(1 , i);
57 this .A.heapSize = this .A.heapSize - 1 ;
58 minHeapify( this .A, 1 );
59 }
60 }
61
62 /**
63 * 使得以index为根的子树成为最大堆
64 *
65 * @param A
66 * int数组
67 * @param index
68 * 以index为根，从1开始
69 */
70 private void maxHeapify(IntArray A, int index) {
71 while (index < A.heapSize / 2 + 1 ) {
72 int left = left(index);
73 int right = right(index);
74 int largest = 0 ;
75 if (left <= A.heapSize && A.aArray[left - 1] > A.aArray[index - 1 ]) {
76 largest = left;
77 } else {
78 largest = index;
79 }
80 if (right <= A.heapSize
81 && A.aArray[right - 1] > A.aArray[largest - 1 ]) {
82 largest = right;
83 }
84 if (index != largest) {
85 exchange(index, largest);
86 index = largest;
87 } else {
88 index = A.heapSize / 2 + 1 ;
89 }
90 }
91 }
92
93 /**
94 * 使得以index为根的子树成为最小堆
95 *
96 * @param A
97 * int数组
98 * @param index
99 * 以index为根，从1开始
100 */
101 private void minHeapify(IntArray A, int index) {
102 while (index < A.heapSize / 2 + 1 ) {
103 int left = left(index);
104 int right = right(index);
105 int smallest = 0 ;
106 if (left <= A.heapSize && A.aArray[left - 1] < A.aArray[index - 1 ]) {
107 smallest = left;
108 } else {
109 smallest = index;
110 }
111 if (right <= A.heapSize
112 && A.aArray[right - 1] < A.aArray[smallest - 1 ]) {
113 smallest = right;
114 }
115 if (index != smallest) {
116 exchange(index, smallest);
117 index = smallest;
118 } else {
119 index = A.heapSize / 2 + 1 ;
120 }
121 }
122 }
123
124 /**
125 * 建最大堆
126 *
127 * @param A
128 * int数组
129 */
130 private void buildMaxHeap(IntArray A) {
131 for ( int i = A.aArray.length / 2; i >= 1; i-- ) {
132 maxHeapify(A, i);
133 }
134 }
135
136 /**
137 * 建最小堆
138 *
139 * @param A
140 * int数组
141 */
142 private void buildMinHeap(IntArray A) {
143 for ( int i = A.aArray.length / 2; i >= 1; i-- ) {
144 minHeapify(A, i);
145 }
146 }
147
148 private int left( int index) {
149 return 2 * index;
150 }
151
152 private int right( int index) {
153 return 2 * index + 1 ;
154 }
155
156 private void exchange( int i, int j) {
157 int temp = A.aArray[i - 1 ];
158 A.aArray[i - 1] = A.aArray[j - 1 ];
159 A.aArray[j - 1] = temp;
160 }
161
162 }
PS：zhuangzhuang1988兄再来一个~O(∩_∩)O哈哈~
标签: 算法
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did49211