继续补数据结构。。。这次记录一下堆排序算法,具体的分析就不班门弄斧了,这两篇文章已经解释的很清楚了(自己脑子慢半天才明白。。)

直接上代码吧

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
#include <iostream>

using namespace std;

/**堆排序**/
void heapIfy(int* num, int dad, int size)
{
int larger = 2*dad + 1; //暂时将较大值指向左孩子
while(larger < size)
{
if(larger+1 < size && num[larger+1] < num[larger]) //找左右孩子中较小的
larger++; //如果右孩子小,就指向右孩子(right = letf+1)

if(num[larger] >= num[dad]) //比较父节点与较小子节点
break;

swap(num[dad], num[larger]); //如果子节点小,与父节点交换
dad = larger; //继续向下比较、交换,直到叶子节点(符合堆的条件)
larger = 2*dad + 1;
}
}

void _heapIfy(int* num, int dad, int size) //递归写法
{
int larger = 2*dad + 1;
if(larger >= size)
return;

if(larger+1 < size && num[larger+1] < num[larger])
larger++;

if(num[larger] >= num[dad])
return;

swap(num[dad], num[larger]);
_heapIfy(num, larger, size);
}

void buildHeap(int* num, int size)
{
/*Tips:
叶子结点已经是合格的堆,直接从叶子的父节点开始整理
叶子 * 2 = 总结点
建堆(大或小)取决于整理方法
*/
for(int i = (size/2 - 1); i >= 0; i--)
minHeapFixDown(num, i, size);
}

void heapSort(int* num, int n)
{
/*
将根结点与最末尾结点交换,删掉最后结点,再整理
最后会整理成一个相反的堆
*/
for(int i = n - 1; i >= 1; i--)
{
swap(num[i], num[0]);
heapIfy(num, 0, i);
}
}

int main()
{
int num[10] = {9, 12, 17, 30, 50, 20, 60, 65, 4};
buildHeap(num, 10);
heapSort(num, 10);
for(int i = 0; i < 10; i++)
cout << num[i] << " ";
return 0;
}

其他

堆这个数据结构在STL中也实现了,需要algorithm这个头文件,速度与我们自己编写相差无几,在STL系列之四 heap 堆这篇文章中有详细说明和测试(ps:还是我大快排厉害~~)
  下次写写归并排序,To be continued~