【数据结构】堆排序(C代码实现 码源)

简介: 【数据结构】堆排序(C代码实现 码源)

一、AdjustUp的基本函数思路

//向上调整,从child开始向上调整
void AdjustUp(HPDataType* a,int child) {
  int parent = (child - 1) / 2;
  while (child>0) {
    if (a[child] > a[parent]) {
      Swap(&a[child], &a[parent]);    //Swap(a[child], a[parent]);  
                                        //传过去的只是a[child]和a[parent]的值,该函数也只是拿形参接收,对原数组并没有产生实质性的影响
                                      //传过去的是地址
      child = parent;
      parent = (parent - 1) / 2;
    }           
    else {
      break;
    }
  }
}



二、AdjustDown的基本函数思路

void AdjustDown(HPDataType* a,int n,int parent) {
  assert(a);
  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;
    }
  }
}

建大堆、小堆用AdjustUP和AdjustDown其实都可以,且不管是从前往后遍历还是从后往前遍历

对比AdjustUP和AdjustDown:Adjustdown的时间复杂度更低 O(N),效率更高

对比分析:

后续有时间的时候会补充讲解,敬请关注



三、堆排序的基本实现思路

//传入堆结构基础——数组,数组大小是判断遍历结束的条件
void HeapSort(HPDataType* a,int n) {
  //升序——建大堆
  //降序——建小堆
  // 建堆--向上调整建堆
  for (int i = 1; i < n; i++) {
    AdjustUp(a,i);
  }
  //建大堆、小堆用AdjustUP和AdjustDown其实都可以,且不管是从前往后遍历还是从后往前遍历
  // 那么就得 建大、小堆时候改变一下a[parent]和a[child]之间的关系
  //对比AdjustUP和AdjustDown之间,Adjustdown的时间复杂度更低,效率更高
  //建堆--向下调整建堆 --O(N)
  for (int i = (n - 1) - 1 / 2; i > 0; i--) {
    AdjustDown(a,n,i);
  }
    //排序
  //升序——建大堆(这里以升序为例)
  //降序——建小堆
  int end = n - 1;
  while (end>0)
  {   
    //max换到最后
    Swap(&a[0],&a[end]);
    --end;   //让它不动,处理剩下的
    //再找到 次max的数 ——重找大堆(不会像直接删除堆顶那样,需要重建堆)
    AdjustDown(a,end,0);
  }
}
目录
相关文章
|
3月前
|
算法 安全 大数据
揭秘!Python堆与优先队列:数据结构的秘密武器,让你的代码秒变高效战士!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue提供堆与优先队列功能,助你提升算法效率。堆用于快速找大数据集的第K大元素,如示例所示,时间复杂度O(n log k)。PriorityQueue在多线程中智能调度任务,如模拟下载管理器,按优先级处理任务。掌握这些工具,让代码运行更高效!
60 1
|
1月前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识,涵盖单链表的定义、优点与缺点,并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现,并提供了尾插法和头插法建立单链表的方法,帮助读者深入理解单链表的基本原理与应用技巧。
123 6
|
1月前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表:顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表,使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作,并提供了具体代码示例。静态分配方式下顺序表的长度固定,而动态分配则可根据需求调整大小。此外,还总结了顺序表的优点,如随机访问效率高、存储密度大,以及缺点,如扩展不便和插入删除操作成本高等特点。
|
1月前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表,常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈,顺序栈使用数组存储,链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛,如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成,链栈则基于单链表的头插法实现。
161 3
|
1月前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。
|
3月前
|
存储 算法
【数据结构】堆,堆的实现,堆排序,TOP-K问题
数据结构——堆,堆的实现,堆排序,TOP-K问题
39 1
【数据结构】堆,堆的实现,堆排序,TOP-K问题
|
2月前
|
搜索推荐 算法
【初阶数据结构篇】插入、希尔、选择、堆排序介绍(上篇)
堆排序(Heapsort)是指利⽤堆积树(堆)这种数据结构所设计的⼀种排序算法,它是选择排序的⼀ 种。它是通过堆来进⾏选择数据。需要注意的是排升序要建⼤堆,排降序建⼩堆。
16 0
|
2月前
|
算法
【初阶数据结构篇】堆的应用(堆排序与Top-K问题)
即求数据结合中前K个最⼤的元素或者最⼩的元素,⼀般情况下数据量都⽐较⼤。
32 0
|
3月前
|
算法 计算机视觉 开发者
燃爆全场!Python并查集:数据结构界的网红,让你的代码炫酷无比!
【7月更文挑战第16天】并查集,Python中的效率明星,处理不相交集合合并与查询。用于社交网络分析、图像处理、图论算法等领域。优雅实现结合路径压缩和按秩合并
30 1
|
3月前
|
搜索推荐
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】