06 April 2013

堆排序是简单选择排序的进化版本,也是使用了选择的思想。简单选择排序是每趟进行顺序遍历选择出最大(小)的元素。而堆排序是通过使用数据结构堆进行选择最大(小)的元素。这两个排序算法唯一的区别也只有这个地方。

下面先介绍数据结构堆的定义:

  • 小顶堆 left { frac{k_{i}leqslant k_{2i+1}}{k_{i}leqslant k_{2i+2}};
  • 大顶堆 left { frac{k_{i}geqslant k_{2i+1}}{k_{i}geqslant k_{2i+2}};
  • 其中,i=0,1,…,left lfloor frac{n}{2} right rfloor。

堆排序的一般步骤(以小顶堆为例):

  • 从最后一个非终端结点left lfloor frac{n}{2} right rfloor开始遍历;
  • 对于每一个遍历到的根结点,比较其左右孩子,选择出最小的结点值,与根结点交换值;
  • 为了保证交换后堆的特性,堆子结点与根节点交换时,如果该子结点还有孩子结点,还要向下进行交换建堆;
  • 堆建成后,删除根结点,用最后一个结点n代替(此操作与简单选择排序操作相似);
  • 继续执行这4步,直到排序完成。

堆的定义类似于完全二叉树,可以理解为完全二叉树所有非终端结点的值不大于(小于)其左、右孩子结点的值。依此规则建堆的话,我们遍历寻找最大(小)结点的步骤就得以简化,堆顶就是我们需要找的值。之前简单选择排序是逐个顺序比较,一趟遍历要执行(n-i+1)次,堆排序是从最后一个非终端结点left lfloor frac{n}{2} right rfloor开始建堆,所以只执行left lfloor frac{n-i+1}{2} right rfloor次。效率增强显而易见。

  • 堆排序使用就地排序,只是删除结点时需要一个临时空间存储变量,其余操作不需要额外的空间,空间复杂度是O(n);
  • 在建堆的比较过程中,从最后一个非空结点开始,所以最多是left lfloor log_{2}n right rfloor+1次,需要执行(n-1)次,所以时间复杂度是Oleft ( nlog n right );
  • 在建堆交换的过程中,只是子结点和双亲比较,所以不稳定。

堆排序实例(以小顶堆为例):

  • 初始序列为:{49,38,65,97,76,13,27,49};
  • 开始建堆,从left lfloor frac{n}{2} right rfloor开始,本例中是第四个结点97,和子结点49比较,子结点较小,进行交换;第三结点65,和子结点13和27进行比较,与较小的13进行交换;第二结点38,与子结点49和76比较,不需要交换;根结点49,与子结点38和13进行比较,与较小的13进行交换。此时第三个结点发生了变动,为了保证堆的特性,还要将该结点与子结点进行比较,使用较小的右子结点27与第三结点49进行交换。{13,38,27,49,76,65,49,97};
  • 删除根结点13,使用最后一个结点97代替;{97,38,27,49,76,65,49},13;
  • 重复建堆,直到所有结点都已排序完成。下面只附上结果,不再复述重复的步骤; 调整堆:{27,38,49,49,76,65,97},13;
  • 删除根结点:{97,38,49,49,76,65},27,13;
  • 调整堆:{38,49,49,97,76,65},27,13;
  • 删除根结点:{65,49,49,97,76},38,27,13;
  • 调整堆:{49,65,49,97,76},38,27,13;
  • 删除根结点:{76,65,49,97},49,38,27,13;
  • 调整堆:{49,65,76,97},49,38,27,13;
  • 删除根结点:{97,65,76},49,49,38,27,13;
  • 调整堆:{65,97,76},49,49,38,27,13;
  • 删除根结点:{76,97},65,49,49,38,27,13;
  • 调整堆:{76,97},65,49,49,38,27,13;
  • 删除根结点:97,76,65,49,49,38,27,13。排序结束,这样建立排序的结果是倒序的,建立小顶堆,结果是递减的序列,建立大顶堆,得到的递增的序列。

原文链接:堆排序(HEAP SORT),转载请注明来源!

EOF

欢迎加微信交流与吐槽



本站总访问量次; 本站访客数人次; 本文总阅读量次;