liyuxia713

蹣跚前行者

常用鏈接

統(tǒng)計(jì)

隨筆 - 50
文章 - 0
評(píng)論 - 32
引用 - 0

Algorithms

lzmagic (rss)
正在更新數(shù)據(jù)結(jié)構(gòu)中的一些經(jīng)典算法
第四維空間
數(shù)據(jù)結(jié)構(gòu) 算法
極限定律
算法

C++

鷹之夢(mèng)園
C++ Primer 學(xué)習(xí)筆記

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

/*
2

* 堆排序
3

* O(nlgn)
4

*/
5

#include <iostream>
7

#include <cstdlib>
8

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

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

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

using namespace std;
14

//交換兩個(gè)元素值
16

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

//輸出數(shù)組元素
18

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

//保持堆性質(zhì)，當(dāng)左右子樹(shù)都是堆時(shí)，但a[i]可能違反堆性質(zhì)時(shí)，調(diào)整成堆
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

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

//創(chuàng)建堆
39

void BuildMaxHeap(int* a, int n)
40

{
41

//從有子樹(shù)的開(kāi)始
42

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

{
44

MaxHeapify(a,i,n);
45

}
46

}
47

void HeapSort(int *a, int n)
49

{
50

//創(chuàng)建堆
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

//交換兩個(gè)元素值
62

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

{
64

int temp = a;
65

a = b;
66

b = temp;
67

}
68

//打印數(shù)組
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

int main()
79

{
80

const int N = 10;
81

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

print(a,N);
84

HeapSort(a,N);
86

print(a,N);
88

system("pause");
90

return 0;
91

}

posted on 2010-01-18 15:45 幸運(yùn)草閱讀(639) 評(píng)論(1) 編輯收藏引用所屬分類(lèi): Algorithms

評(píng)論

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

呵呵，我想請(qǐng)教一下分治法與動(dòng)態(tài)規(guī)劃法，以及貪心法等幾種算法之間的關(guān)系！呵呵，越詳細(xì)越好的！回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

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

liyuxia713

導(dǎo)航

留言簿(3)

隨筆分類(lèi)

收藏夾

隨筆檔案

閱讀排行榜

評(píng)論排行榜

常用鏈接

統(tǒng)計(jì)

Algorithms

C++

最新評(píng)論

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

評(píng)論