加载中…
个人资料
Yode
Yode
  • 博客等级:
  • 博客积分:0
  • 博客访问:595,259
  • 关注人气:250
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

关于堆排序(源代码测试通过)

(2007-04-03 12:51:52)
   昨天在写KNN时,笨笨用到了找出N个数据中的前K个小的数来,这很明显是排序的问题,但是是什么排序呢?笨笨记得原来说过选择排序的时间复杂度相对而言比较小,而且尤其在很多数中选取前几个堆排序作为树形选择排序效果最好。笨笨今天就介绍一下堆排序了。其实堆排序总体来说分为两个大的步骤,第一就是初始建堆并调整堆,第二就是不断输出根结点之后重新调整堆的过程。
   ① 初始如何建堆? 在完全二叉树中,所有序号i>└n/2┘的结点都是叶子,因此,以这些结点为根的子树均已是堆,这样只需将以序号为 └n/2┘, └n/2┘-1, └n/2┘-2,…,1的结点为根、的子树都调整为堆即可。在按此次序调整每个结点时,其左、右子树均已是堆。
② 若ki的左、右子树已经是堆,如何将以ki为根的完全二叉树也调整为堆? 因ki的左、右子树已经是堆,所以就在它的左、右孩子中选出最小(或最大)的结点放到ki的位置上,不妨设k2I关键字最小,将ki与k2I交换位置,而交换之后有可能导致以 k2I为根的子树不再为堆,于是可重复上述过程,将以k2I为根的子树调整为堆,……,如此逐层下去,最多可能一直调整到树叶,此方法称为"筛选法"。源代码如下:
#include "fstream.h"
#include "iostream.h"
#include <stdlib.h>
#include <stdio.h>
#include "string.h"
#include <dos.h>
#include <conio.h>
#include <math.h>
#define MAXSIZE 20 //排序表的最大容量
#define  10
double sample[20]={2,4,6,3,78,34,5,23,98,54,37,80,44,48,91,26,84,20,13,55};
typedef struct //定义排序表的结构
{
    double elemword[MAXSIZE]; //数据元素关键字
    int length; //表中当前元素的个数
}SqList;

void InitialSqList(SqList&); //初始化排序表
void HeapSort(SqList &); //堆排序
void HeapAdjust(SqList &,int,int); //堆调整
void PrintSqList(SqList); //显示表中的所有元素
int pos[20];
void main()
{
    SqList L; //声明表L
    InitialSqList(L); //待排序列初始化
    HeapSort(L); //堆排序
    PrintSqList(L); //显示排序结果
 
}
void InitialSqList(SqList &L)
{//表初始化
    int i;
    L.length=MAXSIZE;
    for(i=0;i<L.length;i++)
    {

        L.elemword[i]=sample[i];
        pos[i]=i;
    }
}
void HeapSort(SqList &L)
   //对顺序表L做堆排序。
    int i;
    double t;
    for(i=L.length/2;i>0;--i) //把L.elemword[1..L.length]建成大顶堆
   
        HeapAdjust(L,i,L.length);
    for(i=L.length-1;i>0;--i)
    {
        t=L.elemword[1]; //将堆顶记录和当前未经排序子序列L.elemword[1..i]
        L.elemword[1]=L.elemword[i]; //中的最后一个记录相互交换
        L.elemword[i]=t;
        HeapAdjust(L,1,i-1); //将L.r[1..i-1]重新调整为大顶堆
    }
}
void HeapAdjust(SqList &H,int s,int m)
{//已知H.elemword[s..m]中除H.elemword[s]之外均满足堆的定义,本函数调整H.elemword[s]
//使H.elemword[s..m]成为一个大顶堆
    double rc;
    int j;
    rc=H.elemword[s];
    for(j=2*s;j<=m;j*=2) //沿关键字叫大的结点向下筛选
    {
        if(j<m&&H.elemword[j]<H.elemword[j+1]) ++j; //j为关键字较大的记录的下标
        if(rc>=H.elemword[j]) break; //rc应插入在位置s上
        H.elemword[s]=H.elemword[j];
        s=j;
    }
    H.elemword[s]=rc; //插入
}
void PrintSqList(SqList L)
{//显示表中所有元素
    int i;
    for(i=0;i<L.length;i++)
   
        printf("%f\t",L.elemword[i]);
    printf("\n");
}


0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有