加载中...

   昨天在写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  K  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");
}