澳门往事txt百度云:9.7.1 堆排序算法（1）

9.7.1 堆排序算法（1）

堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反，便能得到一个有序序列了复执行。

例如图9‐7‐4所示，左图是一个大顶堆，90为最大值，将90与20（末尾元素）互换，如中图所示，此时90就成了整个堆序列的最后一个元素，将20经过调整，使得除90以外的结点继续满足大顶堆定义（所有结点都大于等于其子孩子），见右图，然后再考虑将30与80互换……

相信大家有些明白堆排序的基本思想了，不过要实现它还需要解决两个问题：

1．如何由一个无序序列构建成一个堆？

2．如果在输出堆顶元素后，调整剩余元素成为一个新的堆？

要解释清楚它们，让我们来看代码。

/* 对顺序表L进行堆排序 */  
1 void HeapSort（SqList *L）  
2 {  
3 int i;  
4 for（i=L->length/2;i>0;i--） /* 把L中的r构建成一个大顶堆 */  
5 HeapAdjust（L,i,L->length）;  
6 for（i=L->length;i>1;i--）  
7 {  
8 swap（L,1,i）; /*将堆顶记录和当前未经排序子序列的最后一个记录交换*/  
9 HeapAdjust（L,1,i-1）; /* 将L->r[1..i-1]重新调整为大顶堆 */  
10 }  
11 } 

从代码中也可以看出，整个排序过程分为两个for循环。第一个循环要完成的就是将现在的待排序序列构建成一个大顶堆。第二个循环要完成的就是逐步将每个最大值的根结点与末尾元素交换，并且再调整其成为大顶堆。

假设我们要排序的序列是{50,10,90,30,70,40,80,60,20}5，那么L.length=9，第一个for循环，代码第4行，i是从.9/2.=4开始，4321→→→的变量变化。为什么不是从1到9或者从9到1，而是从4到1呢？其实我们看了图9‐7‐5就明白了，它们都有什么规律？它们都是有孩子的结点。注意灰色结点的下标编号就是1、2、3、4。

注：5 这里把每个数字乘以10，是为了与下标的个位数字进行区分，因为我们在讲解中，会大量的提到数组下标的数字。

我们所谓的将待排序的序列构建成为一个大顶堆，其实就是从下往上、从右到左，将每个非终端结点（非叶结点）当作根结点，将其和其子树调整成大顶堆。i的4→3→2→1的变量变化，其实也就是30，90，10、50的结点调整过程。

既然已经弄清楚i的变化是在调整哪些元素了，现在我们来看关键的HeapAdjust（堆调整）函数是如何实现的。

/* 已知L->r[s..m]中记录的关键字除L->r[s]之外均满足堆的定义 */  
/* 本函数调整L->r[s]的关键字,使L->r[s..m]成为一个大顶堆 */  
1 void HeapAdjust（SqList *L,int s,int m）  
2 {  
3 int temp,j;  
4 temp=L->r[s];  
5 for（j=2*s;j<=m;j*=2） /* 沿关键字较大的孩子结点向下筛选 */  
6 {  
7 if（jr[j]r[j+1]）  
8 ++j; /* j为关键字中较大的记录的下标 */  
9 if（temp>=L->r[j]）  
10 break; /* rc应插入在位置s上 */  
11 L->r[s]=L->r[j];  
12 s=j;  
13 }  
14 L->r[s]=temp; /* 插入 */  
15 } 

1．函数被第一次调用时，s=4，m=9，传入的SqList参数的值为lenth=9,r[10,70,40,20}。

2．第4行，将L.r[s]=L.r[4]=30赋值给temp，如图9‐7‐6所示。

图9-7-6

3．第5～13行，循环遍历其结点的孩子。这里j变量为什么是从2*s开始呢？又为什么是j*=2递增呢？原因还是二叉树的性质5，因为我们这棵是完全二叉树，当前结点序号是s，其左孩子的序号一定是2s，右孩子的序号一定是2s+1，们的孩子以的位数序号增加，因此j变量才是这样循环。

4．第7～8行，此时j=2*4=8，j

5．第9～10行，temp=30,L.r[j]=60，并不满足条件。

6．第11～12行，将60赋值给L.r[4]，并令s=j=8。也就是说，当前算出，以30为根结点的子二叉树，当前最大值是60，在第8的位置。注意此时L.r[4]和L.r[8]的值均为60。