liyuxia713

蹣跚前行者

留言簿(3)

隨筆分類

收藏夾

隨筆檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

隨筆 - 50
文章 - 0
評論 - 32
引用 - 0

Algorithms

lzmagic (rss)
正在更新數據結構中的一些經典算法
第四維空間
數據結構算法
極限定律
算法

C++

鷹之夢園
C++ Primer 學習筆記

基本排序方法及分析（七）：HeapSort 堆排序

1

/*
2

* 堆排序
3

* O(nlgn)
4

*/
5

6

#include <iostream>
7

#include <cstdlib>
8

9

#define LEFT(i) (2*i+1)
10

#define RIGHT(i) (2*i+2)
11

#define PARENT(i) ( (i-1)/2 )
12

13

using namespace std;
14

15

//交換兩個元素值
16

void swap(int& a, int& b);
17

//輸出數組元素
18

void print(int*a, int n);
19

20

//保持堆性質，當左右子樹都是堆時，但a[i]可能違反堆性質時，調整成堆
21

void MaxHeapify(int *a, int i, int n)
22

{
23

int left = LEFT(i);
24

int right = RIGHT(i);
25

int largest = i;
26

27

if(left < n && a[left] > a[largest] )
28

largest = left;
29

if(right < n && a[right] > a[largest])
30

largest = right;
31

if(largest != i)
32

{
33

swap(a[i],a[largest]);
34

MaxHeapify(a,largest,n);
35

}
36

}
37

38

//創建堆
39

void BuildMaxHeap(int* a, int n)
40

{
41

//從有子樹的開始
42

for(int i = PARENT(n-1); i >= 0; i--)
43

{
44

MaxHeapify(a,i,n);
45

}
46

}
47

48

void HeapSort(int *a, int n)
49

{
50

//創建堆
51

BuildMaxHeap(a, n);
52

for(int i = n -1; i >= 1; i--)
53

{
54

//把最大元素放在最后，下一步不予考慮
55

swap(a[i],a[0]);
56

MaxHeapify(a,0,i); //這里不是MaxHeapify(a,0,i-1);
57

}
58

}
59

60

61

//交換兩個元素值
62

void swap(int& a , int& b)
63

{
64

int temp = a;
65

a = b;
66

b = temp;
67

}
68

69

//打印數組
70

void print(int* a , int n)
71

{
72

for(int i = 0; i < n ; i++)
73

cout << a[i] << ",";
74

cout << endl;
75

}
76

77

78

int main()
79

{
80

const int N = 10;
81

int a[N] = {4,1,3,2,16,9,10,14,8,7};
82

83

print(a,N);
84

85

HeapSort(a,N);
86

87

print(a,N);
88

89

system("pause");
90

return 0;
91

}

posted on 2010-01-18 15:45 幸運草閱讀(669) 評論(1) 編輯收藏引用所屬分類: Algorithms

只有注冊用戶登錄后才能發表評論。


相關文章: 基本排序方法及分析（九）：Randomized-Quicksort快速排序的隨機化版本 Order Statistics 順序統計（找出第i小元素）基本排序方法及分析（八）：CoungtingSort 計數排序基本排序方法及分析（七）：HeapSort 堆排序同時求最大最小值基本排序算法及分析（六）：桶式排序基本排序算法及分析（五）：歸并排序基本排序算法及分析（四）：快速排序基本排序算法及分析（三）：shell排序基本排序算法及分析（二）：冒泡排序

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

# re: 基本排序方法及分析（七）：HeapSort 堆排序 2010-10-09 17:55 flyer

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品