首页 > 代码库 > 堆排序

堆排序

2024-07-02 02:19:46   235人阅读

堆排序算法的时间复杂度为O(nlgn).在堆排序算法中，我们使用的是最大堆。

(1)初始时候，堆排序算法利用BUILD-MAX-HEAP将输入数组A[1..n]建成最大堆。

此时堆的根结点是最大元素，且该元素位于数组A[1]。

接着将A[1]与A[n]互换，则可以将A[1..n]中的最大值置于A[n]。

(2)从堆中删除结点n,即使A[n]不再参与后面的计算。

剩余结点中，其他结点没有改变，因此还是最大堆形式，而新替换的

根结点可能会违背最大堆的性质。所以执行MAX-HEAPIFY(A,1)算法,从而在A[1..n-1]上构造一个新的最大堆。

然后将将A[1]与A[n-1]互换，则可以将A[1..n-1]中的最大值置于A[n-1]。

(3)然后堆排序算法会不断重复过程(2)

，直到堆的大小由n-1变成2.

下面给出伪代码

 

下面给出示例代码

 1 package codeforgod;
 2 
 3 /**
 4  * @author gejing gjblmdlm@sina.com
 5  * @version 创建时间：2014年4月29日 下午12:43:30 类说明 :堆排序
 6  */
 7 public class HeapSortDemo {
 8     int heapSize; // 堆元素个数
 9 
10     /**
11      * 堆排序
12      * 
13      * @param a
14      */
15     public void heapSort(int[] a) {
16         buildMaxHeap(a);
17         for (int i = a.length - 1; i > 0; i--) {
18             int temp = a[0];
19             a[0] = a[i];
20             a[i] = temp;
21             heapSize--;
22             maxHeapify(a, 0);
23         }
24 
25     }
26 
27     /**
28      * 建立最大堆
29      * 
30      * @param a
31      */
32     private void buildMaxHeap(int[] a) {
33         heapSize = a.length;
34         for (int i = a.length / 2 - 1; i >= 0; i--) {
35             maxHeapify(a, i);
36         }
37 
38     }
39 
40     /**
41      * 最大堆化
42      * 
43      * @param a
44      * @param i
45      */
46     private void maxHeapify(int[] a, int i) {
47         int l = 2 * (i + 1) - 1; // 左孩子下标
48         int r = 2 * (i + 1);// 右孩子下标
49         int largest = i;
50         if (l < heapSize && a[l] > a[i]) {
51             largest = l;
52         }
53         if (r < heapSize && a[r] > a[largest]) {
54             largest = r;
55         }
56         if (largest != i) {
57             int temp = a[i];
58             a[i] = a[largest];
59             a[largest] = temp;
60 
61             maxHeapify(a, largest);
62         }
63 
64     }
65 
66     public static void main(String[] args) {
67         HeapSortDemo hs = new HeapSortDemo(); // 实例化一个对象
68         int A[] = { 5, 9, 13, 6, 2, 7, 30, 23, 17, 10 };
69         System.out.print("原始序列: ");
70         for (int i : A) {
71             System.out.print(i + "\t");
72         }
73         hs.heapSort(A); // 调用方法进行排序
74         System.out.println();
75         System.out.print("堆排序后: ");
76         for (int i : A) {
77             System.out.print(i + "\t");
78         }
79     }
80 }
View Code

 


联系
我们