堆排序算法-阿里云开发者社区

堆排序算法

2024-02-26 25

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 堆排序算法

虽然在之前的【树】章节，我们已经学习了堆排序。但是这里我们任然要回顾并且补充一些堆排序算法点。

HeapSort堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。

注意的是排升序要建大堆，排降序建小堆。

直接选择排序的特性总结：

1. 堆排序使用堆来选数，效率就高了很多。

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(1)

4. 稳定性：不稳定

整体思路

向下调整算法AdjustDown

建堆（两种方式，主要以向下调整为重点❗）

堆排序

建大堆：升序

建小堆：降序

1：交换头尾

2：向下调整（除去最后一个元素&&最后一个元素已经排好序了）

3：循环重复上述过程，直到全部调整完成

图解分析

【1】向下调整算法

//向下调整
void Adjustdown(int * a, int size, int parent)
{
  //假设法
  int child = parent * 2 + 1;
  while (child < size )
  {
    if (child + 1 < size && a[child + 1] < a[child])//注意❗
    {
      child++;
    }
    //比较
    if (a[child] < a[parent])
    {
      //交换
      Swap(&a[child], &a[parent]);
      parent = child;
      child = child * 2 + 1;
    }
    else//>=
    {
      break;
    }
  }
}

【2】向下调整建堆

//向下调整建堆
  for (int i = (size - 1 - 1) / 2; i >= 0; i--)
  {
    Adjustdown(a, size, i);
  }

【3】排序

void HeapSort(int* a, int size)
{
  //1.向下调整建堆
  for (int i = (size - 1 - 1) / 2; i >= 0; i--)
  {
        //向下调整算法
    Adjustdown(a, size, i);
  }
  //2.排序
  while (size)
  {
    //交换
    Swap(&a[0], &a[size - 1]);
    //向下调整(除去已经排序好的元素）
    Adjustdown(a, size - 1, 0);
    //到达下一个交换的位置
    size--;
  }
}