深入浅出堆排序: 高效算法背后的原理与性能

简介: 深入浅出堆排序: 高效算法背后的原理与性能

⛳️ 推荐

前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。

📋 前言

  🌈堆排序一个基于二叉堆数据结构的排序算法,其稳定性和排序效率在八大排序中也是名列前茅。

  ⛳️堆我们已经讲解完毕了,今天就来深度了解一下堆排序是怎么实现的以及为什么他那么高效。

  📚本期文章收录在《数据结构&算法》,大家有兴趣可以看看呐

  ⛺️ 欢迎铁汁们 ✔️ 点赞 👍 收藏 ⭐留言 📝!

一、堆排序的思想概念

堆排序可以说是排序算法中比较高效的了,既稳定又高效。既然叫堆排序那么肯定离不来堆,基于二叉树来进行构建:

  • 不知道大家发现过没有堆有一个特性
  • 要不就是最大值(大堆)要不然就是一个最小值(小堆)

而我们吧堆顶最大值或最小值进行 pop删除并取出每次的 最大值或者最小值把这些值存储起来

之后他的数据是不是也排序完了,而我们又是用数组来存储的删除不就是把下标 减减吗?

二、堆排序的两种实现方式

堆排序的核心思想就是利用堆的特性来进行数据的取出每次都是最大值或者最小值,那么我得到一组数据要进行堆排序首先:

  • 这组数据需要时堆才能进行排序,那么我们就要开始建堆就完了。

建堆的方法一共有俩种分别是向下取整和向上取整这里都给大家介绍一下

2.1 向上取整

向上取整就是,把新的数据尾插到堆里面然后把他和父节点进行对比调整:

  • 数组存储这里有一个特点 parent = (child-1)/ 2 ;
  • 父节点等于子节点 -1 除二

📚 代码演示:

//向上调整
void adjustup(HeapTypeData* a, int child)
{
  int parent = (child - 1) / 2;
  while (child > 0)
  {
    //建小堆
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (parent - 1) / 2;
    }
    else
    {
      break;
    }
  }
}

2.2 向下取整

向下取整的思想就是把堆顶数据左右子树的的数值进行对比然后向下进行调整:

  • 🔥 向下调整算法有一个前提:左右子树必须是一个堆,才能调整
  • 这里由于是数组存储的所以堆的左右子树都是
  • child = parent* 2+1;
  • 孩子节点的左节点都等于 父节点

    如果堆顶数据和左右子树对比 ,然后再进行调整数据

📚 代码演示:

//向下调整
void adjustdown(HeapTypeData* a, int n, int parent)
{
  int child = parent* 2+1;
  while (child < n)
  {
    if (child+1 < n && a[child + 1] < a[child])
    {
      child++;
    }
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent*2 +1;
    }
    else
    {
      break;
    }
  }
}

三、堆排序的实现代码

3.1 如何利用向上调整建堆

向上调整的思想大家都懂了,而建堆的话我们可以这样想:

  • 从数据的第一个数每次向上调整这样
  • 当调整到最后一个数的时候前面所有的都是已经调整好的堆

📚 代码演示:

//向上调整
void adjustup(HeapTypeData* a, int child)
{
  int parent = (child - 1) / 2;
  while (child > 0)
  {
    //建小堆
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (parent - 1) / 2;
    }
    else
    {
      break;
    }
  }
}
//向上调整建堆  OR 建小堆降序 
//                建大堆升序
for (int i = 1; i < n; i++)
{
  adjustup(a, i);
}

3.1 如何利用向下调整建堆

利用向下调整建堆的要求是左右俩边都是堆才可以向下调整:

  • 那么我们可以把他分为 分治子问题 先向下调整左右子树的在一部部调整堆顶
  • 而堆的最后一个子树一定是堆

这样我们就可以利用数组存储堆的特性 父节点等于子节点 -1除2

  • parent = (child-1)/ 2 ;
  • 然后再利用循环 减减 把每个子树都调整完到堆顶堆就减好了

📚 代码演示:

//向下调整
void adjustdown(HeapTypeData* a, int n, int parent)
{
  int child = parent* 2+1;
  while (child < n)
  {
    if (child+1 < n && a[child + 1] > a[child])
    {
      child++;
    }
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent*2 +1;
    }
    else
    {
      break;
    }
  }
}
//向上调整建堆  OR 建小堆降序 
//                建大堆升序
for (int i = (n-1-1)/2; i > 0; i--)
{
  adjustdown(a, n, i);
}

3.3 堆建完了如何排序数据

堆我们建完了,排序难道一个个把堆顶数据取出然后再放进去吗? 当然不是排序算法都是在数组的 原本空间上进行排序:

  • 我们的思想还是和删除 POP 一样先把堆顶的数据和堆底进行交换
  • 然后再利用下标减减删除数据,(虚拟删除其实还在)
  • 这样每次最大或者最小的数据都被按规律放在原空间里面了

📚 代码演示:

//开始排序
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    adjustdown(a, end, 0);
    end--;
  }

3.4 堆排完整代码

//向上调整
void adjustup(HeapTypeData* a, int child)
{
  int parent = (child - 1) / 2;
  while (child > 0)
  {
    //建小堆
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (parent - 1) / 2;
    }
    else
    {
      break;
    }
  }
}
//向下调整
void adjustdown(HeapTypeData* a, int n, int parent)
{
  int child = parent* 2+1;
  while (child < n)
  {
    if (child+1 < n && a[child + 1] > a[child])
    {
      child++;
    }
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent*2 +1;
    }
    else
    {
      break;
    }
  }
}
void HeapSort(int* a, int n)
{
  //向上调整建堆  OR 建小堆降序 
  //                建大堆升序
  /*for (int i = 1; i < n; i++)
  {
    adjustup(a, i);
  }*/
  for (int i = (n-1-1)/2; i > 0; i--)
  {
    adjustdown(a, n, i);
  }
  //开始排序
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    adjustdown(a, end, 0);
    end--;
  }

四、俩种实现方式的效率对比

4.1 向上调整建堆时间复杂度计算

4.2 向下调整建堆时间复杂度计算

4.3 对比结果

建堆思想 时间复杂度
向上调整建堆 O(N * logN)
向下调整建堆 O(N)

🔥 所以我们在进行堆排序的时候一定首先选取向下调整算法时间复杂度更优。

  • 假设有1000万个数据
建堆思想 排序次数
向上调整 1000W*24(约等于 2亿多)
向下调整 1000W

所以我们向下调整的算法是远远大于向上调整的这是为什么呢?

  • 🔥 因为 向下调整最后一层节点多且全部需要调整到第一层(调整h-1次)
  • 🔥 而向下调整 最后一层不需要调整,越是接近底层调整越少

4.4 堆的时间复杂度计算

📝文章结语:

☁️ 以上就是本章的全部内容了,各位铁汁们快去试试吧!

看到这里了还不给博主扣个:
⛳️ 点赞☀️收藏 ⭐️ 关注

💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖

拜托拜托这个真的很重要!

你们的点赞就是博主更新最大的动力!

有问题可以评论或者私信呢秒回哦。

目录
相关文章
|
16天前
|
机器学习/深度学习 存储 算法
神经网络分类算法原理详解
神经网络分类算法原理详解
27 0
|
26天前
|
算法
经典控制算法——PID算法原理分析及优化
这篇文章介绍了PID控制算法,这是一种广泛应用的控制策略,具有简单、鲁棒性强的特点。PID通过比例、积分和微分三个部分调整控制量,以减少系统误差。文章提到了在大学智能汽车竞赛中的应用,并详细解释了PID的基本原理和数学表达式。接着,讨论了数字PID的实现,包括位置式、增量式和步进式,以及它们各自的优缺点。最后,文章介绍了PID的优化方法,如积分饱和处理和微分项优化,以及串级PID在电机控制中的应用。整个内容旨在帮助读者理解PID控制的原理和实际运用。
64 1
|
1月前
|
机器学习/深度学习 算法 数据可视化
探索线性回归算法:从原理到实践
探索线性回归算法:从原理到实践【2月更文挑战第19天】
21 0
探索线性回归算法:从原理到实践
|
1月前
|
存储 弹性计算 算法
倚天产品介绍|倚天ECS加速国密算法性能
倚天ECS是阿里云基于平头哥自研数据中心芯片倚天710推出arm架构实例,采用armv9架构,支持SM3/SM4指令,可以加速国密算法性能。本文基于OpenSSL 3.2和Tongsuo 实测对比了倚天ECS g8y实例和Intel g7 实例国密性能。为用户选择ECS提供参考。
|
2月前
|
存储 算法 数据库
C++ “雪花算法“原理
C++ “雪花算法“原理
|
4天前
|
机器学习/深度学习 自然语言处理 算法
|
16天前
|
缓存 算法 关系型数据库
深度思考:雪花算法snowflake分布式id生成原理详解
雪花算法snowflake是一种优秀的分布式ID生成方案,其优点突出:它能生成全局唯一且递增的ID,确保了数据的一致性和准确性;同时,该算法灵活性强,可自定义各部分bit位,满足不同业务场景的需求;此外,雪花算法生成ID的速度快,效率高,能有效应对高并发场景,是分布式系统中不可或缺的组件。
深度思考:雪花算法snowflake分布式id生成原理详解
|
17天前
|
搜索推荐 算法
【八大经典排序算法】堆排序
【八大经典排序算法】堆排序
12 0
|
23天前
|
算法
PID算法原理分析及优化
这篇文章介绍了PID控制方法,一种广泛应用于机电、冶金等行业的经典控制算法。PID通过比例、积分、微分三个部分调整控制量,以适应系统偏差。文章讨论了比例调节对系统响应的直接影响,积分调节如何消除稳态误差,以及微分调节如何减少超调。还提到了数字PID的实现,包括位置式、增量式和步进式,并探讨了积分饱和和微分项的优化策略。最后,文章简述了串级PID在电机控制中的应用,并强调了PID控制的灵活性和实用性。
32 1
|
27天前
|
算法 数据库 索引
什么是雪花算法?啥原理?
什么是雪花算法?啥原理?
30 0
什么是雪花算法?啥原理?