《数据结构》排序 —— 堆排序

| |

前言：《数据结构》作为计算机专业的一门重点学科，无论是将来考研、就业，对其的考察都是重中之重，之前的文章已经对此进行过论述。作为考察程序员“编程能力”的一种方式，考验的是我们如何将数据结构的思想用编程语言精确的编码出来。所有的《数据结构》课本都详细的讲解了每一种数据结构和算法的思想，然后给出具体的编程语言代码或者伪代码。算法思想只要认真看书，还是比较容易掌握的 ，真正考验我们的，是从算法思想到具体编码的这个思考过程，就是思考如何编码实现，这个过程是逃不掉的，除非参考别人的现有代码，但一段时间过后一定会忘记（百分之百的，我就忘记了无数次了）。所以，尽量在编程实现前，自己有个清晰的思路，尝试着自己去实现.

代码：
本文全部代码放在 github，需要的可以下载或者直接复制代码运行，只有一个cpp文件。已经通过测试，完全没有问题。这里重点是实现算法思想，所以没有考虑代码的健壮性，没有异常处理。

关四点说明

注意：本文我所说的堆，都指大顶堆。

1）堆的特点是父节点的值大于或等于两个孩子节点的值，一个堆就是一个完全二叉树，所以我们采用数组来存储二叉树，会非常方便。因此，整个数组的序列，也就是一颗二叉树的层次遍历结果（从上到下，从左至右），这一点要知道。

2）建堆的过程：就是从最后一个非终端结点开始，比较其与其孩子节点的大小，如果孩子有比他大的，就交换。如果两个都比他大呢？那就与最大的那个交换。

3）几个需要计算的节点：因为我们是从最后一个非终端结点开始开始遍历，所以要知道它在数组中的位置，知道了它的位置，剩下的只需要依次递减，直到第一个，也就是根节点了。此外，我们还需要知道一个节点的左孩子和右孩子的位置。因为堆是完全二叉树，而且采用数组存储，所以计算还是有规律的。

1
2
3
4
设数组大小为size，一个节点的位置为i（i从1开始）。
最后一个非终端节点的位置：size/2
节点的左孩子位置：2*i
节点的右孩子位置：2*i+1

4）堆排序的流程：给定一个数组，然后建堆——>输出堆的根节点（也就是数组的第一个元素）——>将根节点置为0——>重新建堆——>输出堆的根节点——>……………

附上代码

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
#include <iostream>
using namespace std;
#define ArraySize 8
void create_heap(int data[],int size)
{
	for(int i=(size/2);i>0;i--)	//从最后一个非终端节点开始遍历，直到根节点
	{
		int l_kid=2*i;	//节点的左孩子
		int r_kid=2*i+1;	//节点的右孩子
		int tmp;	//暂存左孩子还右孩子之间最大的那个节点的数组下标
		int k;	//临时变量
		int j=i;
		while(l_kid<=size)	//要遍历到以该节点为根节点的叶子节点
		{
			
			tmp=l_kid;
			if(l_kid<size)	//l_kid<size,说明存在右孩子
			{
				if(data[l_kid-1]<data[r_kid-1])
					tmp=r_kid;
			}
			if(data[j-1]>data[tmp-1])
				break;
			else
			{
				k=data[j-1];
				data[j-1]=data[tmp-1];
				data[tmp-1]=k;
				l_kid=tmp*2;
				j=tmp;
			}
		}
	}
}
void heap(int data[],int size)
{
	create_heap(data,size);//先建堆
	cout<<"建堆完成：";
	for(int i=0;i<ArraySize;i++)
		cout<<data[i]<<" ";
	cout<<endl;
	int data1[ArraySize];	//存放排序后的结果
	for(i=0;i<size;i++)
	{
		data1[i]=data[0];
		data[0]=0;
		create_heap(data,size);
	}
	for(i=0;i<ArraySize;i++)
		cout<<data1[i]<<" ";
	
}
int main()
{
	int data[ArraySize];
	/*输入数组数据*/
	cout<<"请输入8个数："<<endl;
	for(int i=0;i<ArraySize;i++)
		cin>>data[i];
	/*执行排序*/
	heap(data,8);
	/*输出排序结果*/
	cout<<""<<endl;
	
	return 0;
}