2.堆排序 最大堆的向下调整算法 void createHeap (recordnode all, int p, int n)i /*将a[p:n]建立为以a[p]为根的最大堆*/ int 1, j, k i=p;j=2*i;a[0]=a[i;/*a[i]暂存到a[0]中*/ while(j<=n)I if(jn&&a[j.key<a[j+1].key)j++;/*选两子女的较大者*/ if(a[o]. key<alj]. key)( /*a[j移向堆顶*/ ali]=alj]; i=j: j=2*; I else break a[i]=a[0]; 计算机软件技术基础 查找与排序
2. 堆排序 最大堆的向下调整算法 void createHeap(RECORDNODE a[],int p,int n){ /*将a[p:n]建立为以a[p]为根的最大堆*/ int i,j,k; i=p; j=2*i;a[0]=a[i];/*a[i]暂存到a[0]中*/ while(j<=n){ if(j<n&&a[j].key<a[j+1].key) j++;/*选两子女的较大者*/ if(a[0].key<a[j].key){ /*a[j]移向堆顶*/ a[i]=a[j];i=j;j=2*i;} else break; } a[i]=a[0]; } 计算机软件技术基础 查找与排序
2.堆排序 ③对于一个无序序列a[1..n]构成的完全二叉树,只要从 它最后一个非终端结点:(n/2)开始直到根结点为止,逐 步进行上述调整,即可将该完全二叉树调整为堆。 算法为: int p=n/2, i for (i=p; i>=1; i-- createHeap(a, i, n) 计算机软件技术基础 查找与排序
2. 堆排序 ③ 对于一个无序序列a[1..n]构成的完全二叉树，只要从 它最后一个非终端结点：(n/2)开始直到根结点为止，逐 步进行上述调整，即可将该完全二叉树调整为堆。 算法为： int p=n/2,i; for (i=p;i>=1;i--) createHeap(a,i,n); 计算机软件技术基础 查找与排序
2.堆排序 4)堆排序 由以下两个步骤进行: ①由给定的无序序列构造最大堆 ②最大堆堆顶a[1具有最大的关键字,将a[1]与a[n]对调,把具有最 大关键字的对象交换到最后,再对前面的m-1个对象,使用堆的调整算 法 Sieve(a,1,m-1),重新建立最大堆,具有次最大关键字的对象又上 浮到a[1]位置。 ■再对调a[1]和a[n-门,调用 Sieve(a,1,n2),对前n2个对象重新调 整, 如此反复执行,最后得到全部排序好的对象序列。这个算法即堆排 序算法。 计算机软件技术基础 查找与排序
2. 堆排序 4）堆排序 ▪ 由以下两个步骤进行： ① 由给定的无序序列构造最大堆； ② 最大堆堆顶a[1]具有最大的关键字,将a[1]与a[n]对调,把具有最 大关键字的对象交换到最后,再对前面的n-1个对象,使用堆的调整算 法Sieve(a,1,n-1),重新建立最大堆,具有次最大关键字的对象又上 浮到a[1]位置。 ▪ 再对调a[1]和a[n-1],调用Sieve(a,1,n-2),对前n-2个对象重新调 整，…。 ▪ 如此反复执行，最后得到全部排序好的对象序列。这个算法即堆排 序算法。 计算机软件技术基础 查找与排序
2 3 56 56 49 49252125+1608 0825212516|49 初始最大堆 交换0号与5号对象, 5号对象就位 计算机软件技术基础 查找与排序
49 25 25* 21 16 08 1 2 3 4 5 6 49 25 21 25* 16 08 初始最大堆 08 25 25* 16 21 49 1 3 4 5 6 2 08 25 21 25* 16 49 交换 0 号与 5 号对象, 5 号对象就位 计算机软件技术基础 查找与排序
2 3 2 3 56 ¨56"… 25 25|25210816 1625+21082549 从0号到4号重新 交换0号与4号对象, 调整为最大堆 4号对象就位 计算机软件技术基础 查找与排序
25 25* 08 21 16 49 1 2 3 4 5 6 25 25* 21 08 16 49 从 0 号到 4 号 重新 调整为最大堆 4 08 16 25* 25 21 49 1 3 5 6 2 16 25* 21 08 25 49 交换 0 号与 4 号对象, 4 号对象就位 计算机软件技术基础 查找与排序