堆排序

 1 /**
 2  * 堆排序
 3  * 
 4  * @author Administrator
 5  *
 6  */
 7 public class HeapSort {
 8 
 9     public int[] heapSort(int[] array) {
10         
11         int i;
12 
13         // 1.将无序序列构造成一个大顶堆
14         for (i = array.length / 2 - 1; i >= 0; i--) {
15             heapAdjust(array, i, array.length - 1);
16         }
17 
18         // 2.交换堆顶元素与最后一个元素后，然后重新构造大顶堆，重复这个过程
19         for (i = array.length - 1; i > 0; i--) {
20             swap(array, 0, i);
21             heapAdjust(array, 0, i - 1);
22         }
23 
24         return array;
25     }
26 
27 
28     public void heapAdjust(int[] array, int s, int m) {
29 
30         int temp, j;
31         temp = array[s];
32         
33         for (j = 2 * s + 1; j <= m; j = j * 2 + 1) {
34             
35             if (j < m && array[j] < array[j + 1]) {
36                 ++j;
37             }
38             
39             if (temp >= array[j]) {
40                 break;
41             }
42             
43             array[s] = array[j];
44             s = j;
45         }
46 
47         array[s] = temp;
48     }
49 
50     public void swap(int[] array, int i, int j) {
51 
52         int temp;
53         temp = array[i];
54         array[i] = array[j];
55         array[j] = temp;
56     }
57 }