有意思的排序算法-堆排序

　　堆排序，是一個非常優秀的排序算法，像合并排序而不像插入排序，其運作時間為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 }