数据结构-堆排序-题解(C语言代码)

1049 阅读 2 评论 0 点赞

#按题目意思编写的代码

```c
#include <stdio.h>
#include <stdlib.h>
//堆排序算法 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
typedef struct HNode {
	int *data;
	int length;
} *heap,Heap;
void HeapAdgust(heap H, int s, int m){
	int j;
	int rc = H->data[s];
	for(j=2*s; j<=m; j*=2){		//向下筛选 
		if(j<m && H->data[j]<H->data[j+1]) j++;		//取子树更大的值 
		if(rc>=H->data[j]) break;		//此为插入位置，退出循环 
		H->data[s] = H->data[j];
		s = j;
	}
	H->data[s] = rc;
	
}
void HeapSort(heap H){
	int i,temp;
	for(i=H->length/2; i>0; i--){		//把H.[1..H.length]建成大顶堆
		HeapAdgust(H,i,H->length); 
	}
	for(i=H->length; i>0; i--){
		temp = H->data[i];
		H->data[i] = H->data[1];
		H->data[1] = temp;
		HeapAdgust(H,1,i-1);		//将H.[1..i-1]重新调整为大顶堆 
	}
}

void input(heap L){
	for(int i=1; i<=L->length; i++){
		scanf("%d",&L->data[i]);
	}
}
void output(heap L){
	for(int i=1; i<L->length; i++){
		printf("%d ",L->data[i]);
	}
	printf("%d\n",L->data[L->length]);
}
int main(int argc, char *argv[]) {
	Heap L;
	L.data = NULL;
	while(scanf("%d",&L.length) != EOF){
		L.data = (int*)malloc((L.length+1)*sizeof(int));
		input(&L);
		HeapSort(&L);
		output(&L);
		free(L.data);
	} 
	return 0;
}
```

0.0分

0 人评分

本文分类：题解列表
浏览次数：1049 次浏览
发布日期：2019-11-09 15:08:45
本文链接：https://blog.dotcpp.com/a/62527

上一篇 > [编程入门]成绩评定-题解(C语言代码)
下一篇 > 数据结构-KMP算法中的模式串移动数组-题解(C语言代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 2 条评论

一个人的巴黎 3年前回复TA

void HeapSort(int a[],int size)
{
    BuildHeap(a,size);
    for(int i=size-1;i>=0;i--)
    {
        swap(a,0,i);
        down(a,0,i);
    }
}


int main()
{
    int n;
    cin>>n;
    int a[100];
    for(int i=0;i<n;i++)
    cin>>a[i];
    HeapSort(a,n);
    for(int i=0;i<n;i++)
    cout<<a[i]<<' ';
    cout<<endl;
    return 0;
}
两段连起来为什么不对呢，运行错误，给50分，求帮忙看看
/(ㄒoㄒ)/~~

一个人的巴黎 3年前回复TA

#include<iostream>
using namespace std;
void swap(int a[],int x,int y)
{
    int t=a[x];
    a[x]=a[y];
    a[y]=t;
}

void down(int a[],int i,int n)
{
    int parent=i;
    int child=2*i+1;
    while(child<n)
    {
        if(a[child]<a[child+1]&&child+1<n)
        child++;
        if(a[parent]<a[child])
        {
            swap(a,parent,child);
            parent=child;
        }
        child=child*2+1;
    }
}

void BuildHeap(int a[],int size)
{
    for(int i=size/2-1;i>=0;i--)
        down(a,i,size);
}

数据结构-堆排序-题解(C语言代码)

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 2 条评论

发表评论 取消回复

评论列表共有 2 条评论

发表评论取消回复