C语言必学的12个排序算法：堆排序（第7篇）

向右看齐 2023-03-04 10:30 4阅读 0赞

\#题外话堆排序比之前的简单选择、冒泡算法、快速排序算法复杂一些，因为用到了树形数据结构，但是本文使用了数组实现完全二叉树，因此也比较简单。C语言初学者，可以简单了解其思想，具体的知识掌握可以参照数据结构等专业课程学习。

ps：昨天因为学习实在太晚，未及时更新，抱歉哈。学习C语言之余，觉得C语言编程，最重要的就是C语言语法+数据结构+算法，掌握这三方面基本上可以应付各种编程问题。

为什么学习排序算法，可以参见前面文章~\[C语言必学的12个排序算法：基础知识 (第0篇）\]

# 树形选择排序 #

*  选择排序其实可以有简单选择排序、树形选择排序。
 *  其中堆排序是一种高效的树形选择排序。
 *  简单选择排序时间复杂度是O(n^2)，每趟子排序需要比较O(n)次。
 *  树形选择排序通过减少每趟子排序比较次数，减少时间复杂度，基本思想是每趟子排序，对整个数据记录关键字重复两两比较（和锦标赛赛制一样），直至选出最小的关键字记录为止，这样每趟子排序只需要比较O(logn)次，重复n次，即可有序，时间复杂度为O(nlogn)。
 *  普通的树形选择排序需要的辅助空间较多、存在多余的比较的缺点，堆排序改进这些缺点，只需要1个辅助空间，堆排序的时间复杂度是O(nlogn)，同样也是不稳定的内部排序。
 *  与快速排序比较，优势是最坏的情况，堆排序的时间复杂度同样是O(nlogn)，快速排序平均性能比堆排序好，但是最坏情况时间复杂度是O(nlogn)。

# 堆排序 #

堆排序涉及的知识点较多，主要包括堆的定义、完全二叉树，对于C语言初学者来说，具体理论知识可以参见《数据结构》相关课本书籍。

1.完全二叉树

叶子结点只能出现在最后一层或倒数第二层的二叉树。通俗来说，树的父节点都有两个孩子结点，除非是最后一层或倒数第二层的父节点可以有1或0个孩子结点。

2.堆定义

堆首先是完全二叉树，根据父节点是否比孩子节点大，分为大顶堆和小顶堆。

大顶堆：完全二叉树中所有的父节点必须大于等于两个孩子结点，这样树的根结点就是整个树结点中最大值。

小顶堆：完全二叉树中所有的父节点必须小于等于两个孩子结点，这样树的根结点就是整个树结点中最小值。

3.排序过程

以从小到大排序为例，对整个数据记录序列初始建立“大顶堆”，然后根结点为最大关键字，和序列最后一个关键字记录交换，继续对剩下的前n-1个记录序列进行调整，重新变成新的“大顶堆”，如此反复，每次可以得到当前子序列最大的关键字，最后即可得到从小到大的序列。

实现要点：

*   *  从小到大排序，为节约内存空间和方便实现，使用大顶堆；反之从大到小排序，则用小顶堆。
 *   *  重新调整建堆的过程称为筛选，完全二叉树父节点从上到下，沿着关键字较大的孩子节点向下调整，遇到比父节点大的孩子结点，则交换。
 *   *  每次筛选操作后，当前父节点代表的子完全二叉树符合堆的要求，因此对所有父节点筛选后，即可整个符合堆的定义。
 *   *  初始建堆的过程，相当于对所有父节点从“堆顶”筛选操作。
 *   *  初始建立堆时，注意完全二叉树最后一个非叶子结点肯定是\[n/2\]个数据元素，因为其左孩子的结点编号是n/2 \* 2 = n，可以从该元素开始调整建立堆，叶子结点无需调整。

# 代码实现 #

*/
    #include <stdio.h>
    // 对范围[low,high]数据记录筛选调整建立堆
    void adjust_heap(int a[],int low, int high)
    {
       int t = a[low];
       int i;
       // 注意数组下标从0开始
       // 二叉树结点编号需要从1开始 
       // 父节点与孩子结点比较大小，沿着元素路径向下
       for(i=2*(low+1); i<=(high+1); i *= 2)
       {
          // 比较左右孩子结点，如果右孩子大，选择右孩子 
         if(i<=high && a[i-1]<a[i])  i++;
    
         // 如果父节点已经大于等于孩子结点，则调整结束
         if(t>=a[i-1]) 
           break;  
         // 否则调整交换位置
         // 此时不需要给a[i-1]赋值，节约操作
         a[low] = a[i-1];
         low = i-1; 
       } 
       a[low] = t;
    
    } 
    void heap_sort(int a[], int length)
    {
      int i,t; 
    
      // 初始建成大顶堆 
      for(i=length/2-1; i>=0; i--)
      {
        adjust_heap(a, i, length-1);
      }
      // 每趟选出最大元素和当前最后一个元素交换，再调整成堆 
      for(i=length-1; i>=0; i--)
      {
        t = a[0];
        a[0] = a[i];
        a[i] = t;
        adjust_heap(a, 0, i-1);
      }
    }
    int main(void)
    {
        int a[10] = {4,3,1,2,6,5,0,9,8,7};
       heap_sort(a, 10);
        int i;
        for(i=0; i<10; i++)
          printf("%d ", a[i]);
        return 0;
    }

其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。  
![format_png][]  
![format_png 1][]

[format_png]: /images/20230208/0ca5ffd9430048aead6aebf81e6e9c53.png
[format_png 1]: /images/20230208/38541a3b068349a4b837bb1333ead90c.png