|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73 |
#include <iostream>#define len(x) (unsigned int)sizeof(x)/sizeof(x[0])using
namespace std;void
Swap(int
x[],int
i,int j){// int tem = x[i];// x[i] = x[j];// x[j] = tem;//// x[i]^=x[j];// x[j]^=x[i];// x[i]^=x[j]; x[i] = x[i]+x[j]; x[j] = x[i]-x[j]; x[i] = x[i]-x[j];}void
print(int
x[],int
length){ for(int
i = 0; i < length; i++){ cout << x[i] << "\t"; } cout <<endl;}/*heapSort Area*/void
maxHeapify(int
r[],int
heapSize,int
index){ int
left = 2*index+1; int
right = 2*index+2; int
larger = index; if(r[larger] < r[left] && left < heapSize) {//不能有left=heapSize larger = left; }else
larger = index; if(r[larger] < r[right] && right < heapSize){//不能有left=heapSize larger = right; } if(larger!=index){ Swap(r,larger,index); maxHeapify(r,heapSize,larger); }}int
lastNode(int
index){ if(index/2==0) return
(index-1)/2; else
return (index-2)/2;}void
buildMaxHeap(int
r[],int
heapSize){ for(int
i = lastNode(heapSize); i >= 0; i --){ maxHeapify(r,heapSize,i); }}void
heapSort(int
r[],int
length){ int
heapSize = length; buildMaxHeap(r,length); for(int
i = heapSize - 1; i > 0; i--){ Swap(r,0,heapSize-1); cout << r[heapSize-1] << " is put at !"
<< heapSize-1 << endl; heapSize = heapSize-1; maxHeapify(r,heapSize,0); }}int
main(){ int
r[] = {6,7,2,3,8,4,1,9,5,0}; print(r,len(r)); heapSort(r,len(r)); print(r,len(r)); return
0;} |
看了这个ppt和代码应该不会不懂了！
原文：http://www.cnblogs.com/luomingchuan/p/3680490.html