堆排序——我欲修仙（功法篇）

小鱼儿 2024-04-14 06:03 53阅读 0赞

> 个人主页：[【?个人主页】][Link 1]  
> 系列专栏：[【❤️我欲修仙】][Link 2]  
> 学习名言：学习和研究好比爬梯子，要一步一步地往上爬，企图一脚跨上四五步，平地登天，那就必须会摔跤了。——华罗庚

--------------------

![在这里插入图片描述][62037f79f52e428fb03a296198afa688.jpeg_pic_center]

--------------------

## 系列文章目录 ##

第一章 ❤️ [学习前的必知知识][Link 3]  
第二章 ❤️ [二分查找][Link 4]

--------------------

#### 文章目录 ####

*  系列文章目录
 *  前言???
 *  罗伯特·弗洛伊德
 *  堆排序
 *  堆排序原理
 *  代码实现(C语言)

--------------------

## 前言??? ##

> 在数据结构与算法的世界里，有六种常见的排序算法，在之前的故事中我们了解了其中的三种最为基础的算法，今天我们要接触道的可能是六种算法中最难理解的——堆排序

## 罗伯特·弗洛伊德 ##

计算机科学家，图灵奖得主，前后断言法的创始人，堆排序算法和Floyd-Warshall算法的创始人之一。

> 弗洛伊德和威廉姆斯（J．Williams）在1964年共同发明了著名的堆排序算法HEAPSORT  
> 这是与英国学者霍尔 (C.A.R.Hoare，1980年图灵奖获得者）发明的QUICKSORT齐名的高效排序算法之一。此外还有直接以弗洛伊德命名的求最短路的算法，这是弗洛伊德利用动态规划（dynamic programming）的原理设计的一个高效算法。

## 堆排序 ##

> ==堆排序（英语:Heapsort）是指利用堆这种数据结构所设计的一种排序算法。==堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。  
> *堆排序的本质是利用了数据结构中的堆*

![在这里插入图片描述][ee60ee7b0bf746faafc21b4144413472.gif_pic_center]

## 堆排序原理 ##

>  *  大顶堆：每个节点的值都大于或者等于它的左右子节点的值。
>  *  小顶堆：每个节点的值都小于或者等于它的左右子节点的值。
>  *  对于大顶堆：arr\[i\] >= arr\[2i + 1\] && arr\[i\] >= arr\[2i + 2\]
>  *  对于小顶堆：arr\[i\] <= arr\[2i + 1\] && arr\[i\] <= arr\[2i + 2\]
> 
> --------------------
> 
> 在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。  
> 堆中定义以下几种操作：
> 
>  *  最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
>  *  创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
>  *  堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
> 
> --------------------
> 
> 堆排序的基本思路就是：**将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；2、将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；3、重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。**

![在这里插入图片描述][0a970fb378f542c9ae7f8a87d99e362c.gif_pic_center]

## 代码实现(C语言) ##

#include <stdio.h>
    #include <stdlib.h>
     
    void swap(int* a, int* b)
    {
        
        int temp = *b;
        *b = *a;
        *a = temp;
    }
     
    void max_heapify(int arr[], int start, int end) 
    {
        
        //建立父节点指标和子节点指标
        int dad = start;
        int son = dad * 2 + 1;
        while (son <= end)  //若子节点指标在范围内才做比较
            {
        
                if (son + 1 <= end && arr[son] < arr[son + 1]) 
                //先比较两个子节点大小，选择最大的
                son++;
            if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数
                return;
            else  //否则交换父子内容再继续子节点和孙节点比较
            {
        
                swap(&arr[dad], &arr[son]);
                dad = son;
                son = dad * 2 + 1;
            }
        }
    }
     
    void heap_sort(int arr[], int len) 
    {
        
        int i;
        //初始化，i从最後一个父节点开始调整
        for (i = len / 2 - 1; i >= 0; i--)
            max_heapify(arr, i, len - 1);
        //先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
        for (i = len - 1; i > 0; i--) 
        {
        
            swap(&arr[0], &arr[i]);
            max_heapify(arr, 0, i - 1);
        }
    }
     
    int main() {
        
        int arr[] = {
         3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
        int len = (int) sizeof(arr) / sizeof(*arr);
        heap_sort(arr, len);
        int i;
        for (i = 0; i < len; i++)
            printf("%d ", arr[i]);
        printf("\n");
        return 0;
    }

![在这里插入图片描述][2c97942c0d5446b2a8537f29e2ba5d02.gif_pic_center]

[Link 1]: https://blog.csdn.net/weixin_73602725?type=blog
[Link 2]: https://blog.csdn.net/weixin_73602725/category_12259807.html?spm=1001.2014.3001.5482
[62037f79f52e428fb03a296198afa688.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/febfe7b8da314d98a771ad235acf0434.jpeg
[Link 3]: https://blog.csdn.net/weixin_73602725/article/details/129406349
[Link 4]: https://blog.csdn.net/weixin_73602725/article/details/129731407?spm=1001.2014.3001.5501
[ee60ee7b0bf746faafc21b4144413472.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/6f646a658cc24abf95af7b2ae2389117.gif
[0a970fb378f542c9ae7f8a87d99e362c.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/9f8e7f8e4f6b4faeb7cb3f227b2253d8.gif
[2c97942c0d5446b2a8537f29e2ba5d02.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/fc1827021e5d48ef8d29c5afe6e089da.gif