ToB企服应用市场:ToB评测及商务社交产业平台

标题: 堆排序 [打印本页]
作者: 魏晓东    时间: 2024-9-14 04:51
标题: 堆排序
一：头脑

堆排序(Heapsort)是指利用 堆 这种数据结构所筹划的一种排序算法，它是选择排序的一种。它是通过堆来举行选择数据。
动图：



二：实现思路

假设：如今对一个7个整形的数组举行升序堆排（2 1 5 7 4 3 6）效果应该为（1 2 3 4 5 6 7）
第一步：对接受到的数组（2 1 5 7 4 3 6）举行建堆大堆（采取向下调解建堆）

第二步：对得到的大堆，每次交换第一个和最后一个元素，然后输出最后一个元素（最大值），此时最后一个元素不再当作堆里的元素了，最后再把剩下元素重新调解为最大堆，最后输出的就是一个升序的数组！


如上图所示：建立大堆一次，就交换头尾然后end--一次，然后再向下调解建立大堆.....就这样不断举行，最终数组就是1 2 3 4 5 6 7了
总结：

大堆会让最大的在最上面，所以我们把根与最后的元素交换，然后end--，对剩余的继续建大堆...
运用大堆的性质，逐渐的把每次堆里最大的放在数组的最后。
三：代码

  1. //向下调整函数 建立大堆
  2. void AdjustDown(int* a, int n, int parent)
  3. {
  4.         int child = parent * 2 + 1; // 初始化child为parent的左孩子
  5.         while (child < n) // 当child未越界时循环
  6.         {
  7.                 if (child + 1 < n && a[child] < a[child + 1]) // 如果右孩子存在且左孩子大于右孩子
  8.                 {
  9.                         child++; // 将child指向右孩子
  10.                 }
  12.                 if (a[child] > a[parent]) // 如果孩子节点小于父节点，则违反了堆的性质
  13.                 {
  14.                         Swap(&a[child], &a[parent]); // 交换孩子节点和父节点的值
  15.                         parent = child; // 更新parent为交换后的位置
  16.                         child = parent * 2 + 1; // 更新child为新的parent的左孩子
  17.                 }
  18.                 else
  19.                 {
  20.                         break; // 如果父节点已经不大于任何一个孩子节点，则调整完毕，退出循环
  21.                 }
  22.         }
  23. }
  24. //堆排
  25. void HeapSort(int* a, int n)
  26. {
  27.         for (int i = (n - 2) / 2; i >= 0; i--) // 从最后一个非叶子节点开始，直到根节点
  28.         {
  29.                 AdjustDown(a, n, i); // 将每个非叶子节点调整为堆的形式
  30.         }
  31.         int end = n - 1;
  32.         while (end > 0) // 当数组还有元素时
  33.         {
  34.                 Swap(&a[0], &a[end]); // 将堆顶元素（当前最小值）与最后一个元素交换
  35.                 AdjustDown(a, end, 0); // 将剩余的元素重新调整为堆
  36.                 end--; // 减少堆的大小
  37.         }
  38. }
复制代码
解释：

Q1：for (int i = (n - 2) / 2; i >= 0; i--) 

A1：向下调解建堆不是从数组的最后一个元素开始建堆，而是从倒数第一个非叶子节点开始调解（也就是最后一个节点的父亲），根据找父亲的公式parent = （child-1）/2，以为（n-1-1）/ 2，也就是图里的（-2）/2，第一个-1就得到最后一个整数的下标，第二个-1就是公式里的了。
Q2：向下调解的函数解释

堆的实现（看这一篇就够了）-CSDN博客
此篇博客的第六个函数有详细解释。
四：程序运行检测

一万个数据：


十万个数据：

 
一百万个数据


一万万个数据： 

 
五：堆排降序

即向下调解建小堆即可，这样堆顶就是最小的，再交换，最后的就是最小的，然后end--，以此类推 
 
 
 


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4