前言：《数据结构》作为计算机专业的一门重点学科，无论是将来考研、就业，对其的考察都是重中之重，之前的文章已经对此进行过论述。作为考察程序员“编程能力”的一种方式，考验的是我们如何将数据结构的思想用编程语言精确的编码出来。所有的《数据结构》课本都详细的讲解了每一种数据结构和算法的思想，然后给出具体的编程语言代码或者伪代码。算法思想只要认真看书，还是比较容易掌握的 ，真正考验我们的，是从算法思想到具体编码的这个思考过程，就是思考如何编码实现，这个过程是逃不掉的，除非参考别人的现有代码，但一段时间过后一定会忘记（百分之百的，我就忘记了无数次了）。所以，尽量在编程实现前，自己有个清晰的思路，尝试着自己去实现，然后调试，脑细胞不够用了再去参考别人写的。
0、代码：
本文全部代码放在 github：https://github.com/thinkChao/Data-Structure/blob/master/%E5%A0%86%E6%8E%92%E5%BA%8F.cpp 中，需要的可以下载或者直接复制代码运行，只有一个cpp文件，已经通过测试。
1、关于堆排序的四点说明（注意：本文我所说的堆，都指大顶堆。）：
1）、堆的特点是父节点的值大于或等于两个孩子节点的值，一个堆就是一个完全二叉树，所以我们采用数组来存储二叉树，会非常方便。因此，整个数组的序列，也就是一颗二叉树的层次遍历结果（从上到下，从左至右），这一点要知道。
2）、建堆的过程：就是从最后一个非终端结点开始，比较其与其孩子节点的大小，如果孩子有比他大的，就交换。如果两个都比他大呢？那就与最大的那个交换。
3）、几个需要计算的节点：因为我们是从最后一个非终端结点开始开始遍历，所以要知道它在数组中的位置，知道了它的位置，剩下的只需要依次递减，直到第一个，也就是根节点了。此外，我们还需要知道一个节点的左孩子和右孩子的位置。因为堆是完全二叉树，而且采用数组存储，所以计算还是有规律的。
设数组大小为size，一个节点的位置为i（i从1开始）。
最后一个非终端节点的位置：size/2
节点的左孩子位置：2*i
节点的右孩子位置：2*i+1
4）、堆排序的流程：给定一个数组，然后建堆——>输出堆的根节点（也就是数组的第一个元素）——>将根节点置为0——>重新建堆——>输出堆的根节点——>……………
3、附上代码：
#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;
}
网友评论