前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C 语言实现堆排序 (Heap Sort)

C 语言实现堆排序 (Heap Sort)

作者头像
caoqi95
发布2019-05-13 20:34:37
1.7K0
发布2019-05-13 20:34:37
举报
文章被收录于专栏:caoqi95的记录日志

堆排序是一种基于「堆」这一数据结构的排序算法。堆是一种近似完全二叉树的结构,分为大顶堆和小顶堆这两种。

  • 大顶堆:子节点的值总是小于其父节点的值。
  • 小顶堆:子节点的值总是大于其父节点的值。

如果使用大顶堆的话,最后的排序结果会是升序;如果采用小顶堆的话,最后的排序结果会是降序。

使用大顶堆实现数字大小排序

首先会使用大顶堆来实现数字的从小到大排序,主要分为下面 3 个过程:

  • 最大堆调整:将堆的末端子节点做调整,使得子节点小于父节点。
  • 创建最大堆:将堆中所有数据排序成大顶堆的形式。
  • 堆排序:将顶端数据和最末尾数据交换位置,然后做最大堆调整的递归运算。

实现代码如下所示:

使用小顶堆实现字符串大小排序

和大顶堆的过程一样,只是有些微小的差别:

  • 最小堆调整:将堆的末端子节点做调整,使得子节点大于父节点。
  • 创建最大堆:将堆中所有数据排序成小顶堆的形式。
  • 堆排序:将顶端数据和最末尾数据交换位置,然后做最小堆调整的递归运算。

实现代码如下所示:

具体代码可见这个 repo 中的 Homework-4mid-exam

参考:

[1]. 堆排序 - 维基百科 [2]. 图解排序算法(三)之堆排序

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019.05.01 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 使用大顶堆实现数字大小排序
  • 使用小顶堆实现字符串大小排序
  • 参考:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档