数据结构排序（堆排序）-白红宇

数据结构排序（堆排序）

阅读量：6452 次

发布时间：2019-06-23

本文共 3761 字，大约阅读时间需要 12 分钟。

//最小堆的特性说明:即任何一非叶节点的值不大于其左右孩子节点的值。//堆排序最适合取TOPN的数据#include "myheap.h"int myswap(int *src, int *desc){    int tmp = 0;    tmp = *src;    *src = *desc;    *desc = tmp;    return 0;}//调整树//@arr 需要排序的数组//@root 根节点//@size 树的大小int changeTree(int *arr,int root, int size){    int leftnode = 2 * root;//左孩子节点序号    int rightnode = 2 * root + 1;//右孩子节点序号    int pos = 0;//孩子节点中值最大的序号    int tmp = 0;    if (leftnode > size)    {        //左孩子的序号大于整个树的节点数，这是非法的        return -1;    }    if (rightnode > size)    {        //这颗树只有左孩子节点        pos = leftnode;    }    else    {        //左孩子右孩子节点都存在，取左孩子右孩子节点中值最大的节点        pos = arr[leftnode - 1] < arr[rightnode - 1] ? leftnode : rightnode;    }    //调整堆    if (arr[root - 1] > arr[pos - 1])    {        myswap(arr + root - 1, arr + pos - 1);        //重新调整树        changeTree(arr, pos, size);    }    return 0;}//创建堆int buildHeap(int *arr){    //创建最小堆    //找到整个树末尾的非叶子节点 正好是 树的节点数/2    int pos = K / 2;    for (pos; pos >= 1; pos--)    {        //一开始为无序一组数，需要构建堆，堆需要满足堆的特性        changeTree(arr, pos, K);    }    return 0;}//堆排序//@source 无序数组//@desc 最终生成TOP N数组//@size 无序数组的长度//注意:desc数据就是从source中直接截取N个数据,source不能再有desc的数据，是截取，而不是拷贝int heapSort(int *source,int *desc,int size){    int i = 0;    buildHeap(desc);    //树的堆排序--无序数组中的数据向有序数组中插入    for (i = 0; i < size; i++)    {        //如果堆中最小的值的节点，说明N数组中有更大的值，将当前堆中的最小值从堆剔除        //并且将N数组中大的值加进来，重新调整堆        if (desc[0] < source[i])        {            myswap(desc, source + i);            //重新调整堆，因为根节点的值变了,导致堆不再是堆了，所以从根节点开始            changeTree(desc,1, K);        }    }    //注意：堆排序只能获取海量数组前TOPN的数据，但是TOP N的数组不是有序的，继续才能获取完整的序列    //推荐：小数据完全有序，不建议使用堆排序，经过我的测试，似乎速度并不快,可以使用快速排序    for ( i = K-1; i > 0; i--)    {        //这样堆顶元素又不是最小的了        //desc[i]=desc[0];        myswap(desc, desc + i);        //重新调整堆--本质上堆变小了        changeTree(desc, 1, i);    }    return 0;}

#define _CRT_SECURE_NO_WARNINGS#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include "myheap.h"#define NUMCOUNT 100*10000int getTimestr(char * buf){    time_t tData = 0;    //获取当前系统时间    time(&tData);    //定义时间结构体变量    struct tm * eventTime = NULL;    //将time_t类型转化成时间结构体类型    eventTime = localtime(&tData);    //tm_year表示年份，以1900为标准，1900的值是0,1901的值是1    int iyear = eventTime->tm_year + 1900;    //tm_mon表示月份，从0开始到11结束，按照通常习惯应该从1月份开始    int imon = eventTime->tm_mon + 1;    //tm_wday:表示一个星期的第几天 从1开始7结束    //tm_yday:表示一年的第几天    //tm_mday:表示正常的月天数    int iday = eventTime->tm_mday;    //时分秒    int ihour = eventTime->tm_hour;    int imin = eventTime->tm_min;    int isec = eventTime->tm_sec;    //拼接时间    char timestr[30] = { 0 };    sprintf(timestr, "%04d-%02d-%02d %02d:%02d:%02d", iyear, imon, iday, ihour,        imin, isec);    strcpy(buf, timestr);    return 0;}//随机产生100万数据int createNumber(int *arr){    int i = 0;    //定义一个时间类型    time_t ts;//头文件time.h    //生成随机数种子    srand((unsigned int)(time(&ts)));    //创建出5个大数    arr[0] = 10001;    arr[1] = 10002;    arr[2] = 10005;    arr[3] = 10007;    arr[4] = 10009;    for (i = 5; i < NUMCOUNT; i++)    {        //随机产生1000以内的树        arr[i] = (int)(rand() / 1000);    }    return 0;}void test(){    int i = 0;    char timebuf[1024] = { 0 };    int desc[K] = { 2,3,4,5 };    int *soruce = (int *)malloc(sizeof(int)*NUMCOUNT);    if (NULL == soruce)    {        perror("malloc");        return;    }    memset(soruce, 0, sizeof(int)*NUMCOUNT);    createNumber(soruce);    getTimestr(timebuf);    printf("begin=%s\n", timebuf);    heapSort(soruce, desc, NUMCOUNT);    for (i = 0; i < K; i++)    {        printf("%d\n",desc[i]);    }    memset(timebuf,0,1024);    getTimestr(timebuf);    printf("end=%s\n", timebuf);    free(soruce);    soruce = NULL;}int main(){    test();    system("pause");    return 0;}