数据结构C语言版之堆排序（代码）

深碍√TFBOYSˉ_ 2022-04-06 05:46 170阅读 0赞

之前写了直接插入和折半插入的排序算法，这次的是堆排序算法，相比前两种，这种的时间复杂度更低一些，在一些题目里面，有可能你用其他的排序方法就会超时，而用堆排序就不会。

堆的定义什么的就略去了

代码：

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #define MAX_SIZE 10000
    //typedef struct {
    //    int r[MAX_SIZE+1];
    //    int Length;
    //}
    void HeapAdjust(int *a,int head,int tail);
    void heapSort(int a[],int len);
    
    int main(){
        int M,N;
        scanf("%d%d",&M,&N);
        int a[M];
        int i;
        for(i = 0; i < M;i++){
            scanf("%d",&a[i]);
        }
        int n = M;
        heapSort(a,n);
    
        for(i = M-1; i >= M-N && i>= 0; i--){
            if(i == M-1)
                printf("%d",a[i]);
            else
                printf(" %d",a[i]);
        }
    }
    
    void HeapAdjust(int *a,int head,int tail){
        int tmp = a[head];
        int j = 2*head+1;
        int i = head;
        while(j <= tail){
            if(j < tail && a[j] < a[j+1])
                ++j;
            if(tmp < a[j]){
                a[i] = a[j];
                i = j;
                j = 2*i+1;
            }
            else
                break;
        }
        a[i] = tmp;
    }
    void heapSort(int a[],int n){
        int i;
        int tmp;
        for(i = n/2-1; i >= 0; --i){
            HeapAdjust(a,i,n-1);
        }
        for(i = n-1; i > 0;--i){
            tmp = a[0];
            a[0] = a[i];
            a[i] = tmp;
            HeapAdjust(a,0,i-1);
        }
    }

注：可以去B站搜一下堆排序，有个相关视频可以帮助理解！

发表评论取消回复

表情：

评论列表（有 0 条评论，170人围观）

还没有评论，来说两句吧...

相关阅读

相关【大话数据结构C语言】68 堆排序

堆排序算法是利用堆进行排序的方法基本思想是将待排序的序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾

约定不等于承诺〃/ 2022年10月15日 00:47/ 0 赞/ 132 阅读

相关 C语言数据结构-排序-堆辅助函数

堆辅助函数二叉堆是完全二叉树或者是近似完全二叉树。二叉堆有两种：最大堆和最小堆。最大堆(大顶堆)：父结点的键值总是大于或等于任何一个子节点的键值，即最大的元素

「爱情、让人受尽委屈。」/ 2022年10月07日 11:46/ 0 赞/ 149 阅读

相关 C语言数据结构-排序-堆化

堆化二叉堆一般用数组来表示。例如，根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2。因此，第0个位置的子节点在1和2，1的子节点在3和4。以此类

桃扇骨/ 2022年10月07日 11:46/ 0 赞/ 149 阅读

相关 C语言数据结构-排序-堆元素插入

堆元素插入二叉堆一般用数组来表示。例如，根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2。因此，第0个位置的子节点在1和2，1的子节点在3和4。

浅浅的花香味﹌/ 2022年10月07日 11:46/ 0 赞/ 143 阅读

相关 C语言数据结构-排序-堆初始化

堆初始化二叉堆一般用数组来表示。例如，根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2。因此，第0个位置的子节点在1和2，1的子节点在3和4。以

傷城~/ 2022年10月07日 11:46/ 0 赞/ 143 阅读

相关数据结构之堆排序

package com.zhiru; / 堆排序时间复杂度：O(nlog2n) 空间复杂度：O(1)

以你之姓@/ 2022年08月11日 17:30/ 0 赞/ 140 阅读

相关 C语言-数据结构-堆排序（heap sort）-源代码

1. 堆排序堆排序的定义及思想可以参考百度百科：[堆排序][Link 1] 用一句概括，堆排序就是一种改进的选择排序，改进的地方在于，每次做选择的时候，不单单把最大的数字

r囧r小猫/ 2022年07月11日 12:11/ 0 赞/ 165 阅读

相关数据结构C语言版之堆排序（代码）

之前写了直接插入和折半插入的排序算法，这次的是堆排序算法，相比前两种，这种的时间复杂度更低一些，在一些题目里面，有可能你用其他的排序方法就会超时，而用堆排序就不会。堆的定义

深碍√TFBOYSˉ_/ 2022年04月06日 05:46/ 0 赞/ 171 阅读

相关 C语言数据结构堆排序算法

/\ \堆排序（heapsort）是选择排序的升级版降低了排序函数的冗余性 \堆排序分为大顶堆和小顶堆大顶堆为堆顶为最大元素小顶堆为堆顶为最小元素 \先

Bertha 。/ 2022年01月21日 23:57/ 0 赞/ 218 阅读

相关 C++数据结构--堆排序

popHeap() ,adjustHeap()详见 [C++数据结构--用向量数组实现大（小）根堆的插入和删除][C_--] 1.对已经堆化的数组进行堆排序

Love The Way You Lie/ 2021年11月10日 14:20/ 0 赞/ 296 阅读