学步园

1:今天看了堆排序总觉得似懂非懂的，下午自习了解了一下已经独立完成C代码的堆排序，我先描述一下然后放出代码，最终会放出来和数据结构课本上完全一致的代码。

2：堆排序时利用堆得性质，也就是二叉树的根节点要么小于两个子节点，那么大于2个子节点。堆排序中是首先建立的根节点大于子节点的堆，也就是说的大堆。

3：建立好大堆之后，root点的元素最大，于是把root和最后一个元素调换位置，接着再对前n-1个元素构建成为一个大堆，接着继续把root点和n-1点对换，接着，。。。。一直到只剩下一个节点的时候就不用再构建大堆了，就可以了。

因为root和最后一个节点兑换之后，此时之后根节点所在的树不一定完全符合堆得概念，所以首先调整第一棵树，保证头结点比两个孩子结点都大，条换完后可能子树出现不符合的，然后再调换，知道调换到符合或者该节点跑到了叶子上为止。

所以这个过程一共2个方法，一个事构建堆，一个事兑换完之后对剩下的再构建堆。

这2个都是构建堆，但是初始化的构建堆是从i = n/2的节点一致到i=1的节点构建的，而剩下的再构建堆是从i=1开始构建的，所以不是完全的相同，但是也可以到最后弄成一个函数，书上就是这么写的（其实觉得书上应该写的越是容易理解猜对，而发现书上总是故意绕圈子写的很简洁以至于很多地方难懂了）。根据这个思路我先弄上去代码。

#include <stdlib.h><br /> #include <stdio.h></p> <p>#define MAX_SIZE 20<br /> typedef int ElemType; </p> <p>// 定义排序表<br /> typedef struct HeapList<br /> {<br /> ElemType *keys;<br /> int length;<br /> }HeapList;</p> <p>// 初始化排序表<br /> void InitHeapList(HeapList &L)<br /> {<br /> L.keys = (ElemType*)malloc(MAX_SIZE * sizeof(ElemType));<br /> L.length = 6;<br /> int data[] = {38, 11, 9, 27, 96, 83};<br /> for(int i = 0; i < 6; ++i)<br /> L.keys[i + 1] = data[i];<br /> }</p> <p>// 打印排序表<br /> void PrintHeapList(HeapList &L)<br /> {<br /> for(int i = 1; i <= L.length; ++i)<br /> printf("%5d", L.keys[i]);<br /> printf("/n");<br /> }</p> <p>//初始化大堆<br /> void CreateBigHeap(HeapList &L)<br /> {<br /> int middle = L.length/2;<br /> for(int i = middle; i > 0; i--)<br /> {<br /> if(((2*i + 1) > L.length) && (2*i <= L.length))<br /> {<br /> // 当没有右字树的时候只判断根节点和左字树的大小进行调换<br /> if(L.keys[i] < L.keys[2*i])<br /> {<br /> L.keys[0] = L.keys[i];<br /> L.keys[i] = L.keys[2*i];<br /> L.keys[2*i] = L.keys[0];<br /> }<br /> }<br /> if((2*i + 1) <= L.length)<br /> {<br /> // 左右子数都有<br /> // 先比较左右字树哪个最大<br /> int max = 2 * i;<br /> if(L.keys[2*i] < L.keys[2*i + 1])max++;<br /> if(L.keys[i] < L.keys[max])<br /> {<br /> L.keys[0] = L.keys[i];<br /> L.keys[i] = L.keys[max];<br /> L.keys[max] = L.keys[0];<br /> }<br /> }<br /> }<br /> }</p> <p>// 初始化大堆之后，每一次的对前N-1个进行再次大堆<br /> void heapfy(HeapList &L, int end)<br /> {<br /> //此时出去root节点，其余的还是都符合大堆的，可以从头结点和他的子节点对比较，一直比到没有没有孩子结点或者满足大堆的时候停止<br /> for(int i = 1; 2*i <= end; i *=2)<br /> {<br /> if(2*i + 1 <= end)<br /> {<br /> // 还是三者对比，然后把i更新到替换到得为之<br /> int max = 2*i;<br /> if(L.keys[2*i] < L.keys[2*i + 1])max++;<br /> // 右字树最大，那么把该字树根节点和他对换吧<br /> L.keys[0] = L.keys[i];<br /> L.keys[i] = L.keys[max];<br /> L.keys[max] = L.keys[0];<br /> // 切记，更新i的位置<br /> i = max;<br /> // 接下来跳出if，进入for的下一个循环，该此时继续把i的自树进行如上操作<br /> }<br /> if(2*i + 1 > end && 2*i <= end)<br /> {<br /> // 只有左子树啦<br /> if(L.keys[i] < L.keys[2*i])<br /> {<br /> L.keys[0] = L.keys[i];<br /> L.keys[i] = L.keys[2*i];<br /> L.keys[2*i] = L.keys[0];<br /> }<br /> }<br /> }<br /> }</p> <p>// 堆排序<br /> void HeapSort(HeapList &L)<br /> {<br /> // 初始化一次大堆<br /> CreateBigHeap(L);<br /> // 把第一个和最后一个调换一下<br /> L.keys[0] = L.keys[1];<br /> L.keys[1] = L.keys[L.length];<br /> L.keys[L.length] = L.keys[0];<br /> for(int i = L.length - 1; i > 0; --i)<br /> {<br /> heapfy(L, i);<br /> L.keys[0] = L.keys[1];<br /> L.keys[1] = L.keys[i];<br /> L.keys[i] = L.keys[0];<br /> }<br /> } </p> <p>void main()<br /> {<br /> HeapList L;<br /> InitHeapList(L);<br /> PrintHeapList(L);<br /> HeapSort(L);<br /> PrintHeapList(L);<br /> }

这个代码保证正确，我本地已经写出来测试过的了。