| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1289 人关注过本帖
标题:堆排序
只看楼主 加入收藏
点线面
Rank: 8Rank: 8
来 自:NO.-1
等 级:蝙蝠侠
帖 子:525
专家分:980
注 册:2011-1-3
收藏
得分:0 
回复 10楼 犬虫门心
不用面对面,将图形表达清楚就OK,毕竟还是要自己领悟,
授人以鱼,不如授人以渔。

小代码,大智慧
2011-01-26 19:55
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
那按照你这么说我这个程序有问题,为什么还能正确排序呢?

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-26 20:13
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
首先,你要看懂代码, 得先知道堆的概念,并且了解堆排序的基本原理,
仅仅是看别人写的这种"破烂不堪"的代码, 是很难看的懂的。
如果花太多的精力"去其糟粕,取其精华", 投入与产出成反比。

堆排序分两步,

第一步:将不规则数组修正为堆,(这里你就需要知道什么是堆)

第二步:将数组的首元素与数组的尾元素交换, 并不断的修正堆
这个类似于优先队列,不断的数组的 最大的/或最小的元素移动到数组的尾部,最终形成一个排好序的数组


[ 本帖最后由 BlueGuy 于 2011-1-27 17:03 编辑 ]

我就是真命天子,顺我者生,逆我者死!
2011-01-27 17:02
pangding
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:北京
等 级:贵宾
威 望:94
帖 子:6784
专家分:16751
注 册:2008-12-20
收藏
得分:0 
堆排就是这 BG 说的这两步。
楼主自己动手把 make heap 和 sort heap 的过程搞清楚就行了。等理解好了之后,看其它的代码应该会轻松一些。不能对着别人的代码蒙这个过程。
2011-01-28 23:41
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
理解过程后,发现如果程序的下标是从0开始,那么树的左孩子是2k+1,右孩子是2k+2,贴上自己的程序,请各位高手看看还有什么错误?
#include <stdio.h>
#include <stdlib.h>
FILE *fin,*fout;
void file_start()
{
if((fin=fopen("hsort.in","r"))==NULL)
{
printf("Cannot open this file!\n");
getchar();
exit(0);
}
if((fout=fopen("hsort.out","w"))==NULL)
{
printf("Cannot open this file!\n");
getchar();
exit(0);
}
}
void sift(int startPos,int endPos,int number[])
{
 //startPos是完全二叉树(堆)中,当前要处理的节点编号
 //endPos是当前要处理的堆中的元素个数
 //number是堆本身
 //根据下面主调函数的实参,可以知道,startPos的值应该是长度为endPos的完全二叉树中的最后一个非叶子节点的编号
 int k=2*startPos+1,temp;//根据完全二叉树的性质,编号为startPos的节点的左孩子的编号应该是2*startPos+1,那么k就是startPos节点的左孩子节点
 temp=number[startPos];//保存当前父亲节点的值,有可能覆盖
 while(k<endPos)//如果还有中间节点没有处理完
 {
 if(k+1<endPos&&number[k]<number[k+1]) k++; //number[k]和number[k+1]分别是number[i]的左、右孩子,这是在找值最大的孩子
 if(temp<number[k])//如果孩子比其父节点的值都大的话,则覆盖父节点的值,看来这是要形成“大根堆”
 {
  number[startPos]=number[k];//覆盖操作
  startPos=k;//让节点指针移动到值交换之后的子节点处
  k=2*startPos+1;//k依然指向i的左孩子节点
 }
 else
 break;//如果没有交换,即number[i]、number[k]和number[k+1]所构成的堆本身满足大根堆,则不需要再向下继续了
 }
 number[startPos]=temp;//将函数一开始要移动的number[i]的值,移动到现在(可能移动、也可能没有移动)的number[i]里
}
void heap_sort(int number[],int n)
{
int i,temp=0;
for(i=n/2;i>=0;i--)
sift(i,n,number);
for(i=n-1;i>=0;i--)
{
  temp=number[i];
  number[i]=number[0];
  number[0]=temp;
  sift(0,i,number);
}
}
int main()
{
int i,number[10000]={0},n;
file_start();
fscanf(fin,"%d",&n);
for(i=0;i<n;i++)
fscanf(fin,"%d",&number[i]);
heap_sort(number,n);
for(i=0;i<n;i++)
fprintf(fout,"%d ",number[i]);
system("pause");
return 0;
}

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-29 09:23
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-29 11:12
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
各位高手看看还有什么错误?

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-29 13:27
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
这个程序已经能正确运行了,且结果正确

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-29 14:04
快速回复:堆排序
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.054472 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved