返回顶部

收藏

C语言堆排序从N个数中找出最大的10个数

更多
/* 
 * author: goosman.lei
 * mail: lgg860911@yahoo.com.cn
 * blog: http://blog.csdn.net/lgg201
 */

#include <stdio.h>  
#include <time.h>  
#include <stdlib.h>  
#include <unistd.h>  
#include <strings.h>  

#define BUFF_LEN    (4096)  

#define PARENT(i)   ((i) / 2 - 1)  
#define LEFT(i)     ((i + 1) * 2 - 1)  
#define RIGHT(i)    ((i + 1) * 2)  

/* #define DEBUG */  
#define INFO  

#ifdef INFO  
    int     s_0, s_1, s_2;  
    struct timeval  begin, end;  
#endif  

typedef struct queue_s  queue_t;  
struct queue_s {  
    int     data;  
    queue_t *next;  
};  

static void generate_test_data(long n) {  
    long    i;  
    int     r;  
    int     l;  

    l   = sizeof(int);  
    srand(time(NULL));  
    for ( i = 0; i < n; i ++ ) {  
        r   = rand();  
        fprintf(stdout, "%d\n", r);  
        write(STDERR_FILENO, &r, l);  
    }  
}  
static int read_input(int fd, void *buff, int buff_len) {  
    int     i, ret;  

    for ( i = 0; i < buff_len; ) {  
        ret = read(fd, buff, BUFF_LEN);  
        if ( -1 == ret ) {  
            perror("read error\n");  
            exit(0);  
        } else if ( 0 == ret ) {  
            break;  
        } else {  
            buff    += ret;  
            i       += ret;  
        }  
    }  
    return i;  
}  

static void dump_link(queue_t *q, int n) {  
    for ( ; q != NULL; q = q->next )  
        fprintf(n ? stderr : stdout, "%d\n", q->data);  
    if ( n ) printf("\n");  
}  

void max_heapify(int *sbuff, int j) {  
    int i;  
#ifdef INFO  
    s_0 += 3;  
    s_1 ++;  
#endif  
    if ( sbuff[j] < sbuff[LEFT(j)] )  
        i   = LEFT(j);  
    else  
        i   = j;  
    if ( sbuff[i] < sbuff[RIGHT(j)] ) {  
        i   = RIGHT(j);  
#ifdef INFO  
    s_1 ++;  
#endif  
    }  
    if ( i != j ) {  
        sbuff[i]    ^= sbuff[j];  
        sbuff[j]    ^= sbuff[i];  
        sbuff[i]    ^= sbuff[j];  
        max_heapify(sbuff, i);  
#ifdef INFO  
    s_1 += 3;  
#endif  
    }  
}  
int main(int argc, char *argv[]) {  
    int     *sbuff, *rbuff, *rbuff_t;  
    int     i, j, n, rbuff_n;  

    if ( argc < 2 ) {  
        printf("usage: \n\t1. 生成测试数据: %s <number> /* 标准错误以二进制方式输出测试数据, 标准输出以文本方式输出测试数据用于脚本校验 */\n\t2. 执行Top 10查找: %s <exec> /* 标准输出输出前10个最大数据(倒序), 开启INFO时在标准错误输出统计信息, 开启DEBUG时在标准错误输出调试信息\n",   
            argv[0], argv[0]);  
        return (0);  
    }  
    if ( strcmp(argv[1], "exec") != 0 ) {  
        /* 不考虑数字输入的容错了 */  
        generate_test_data(atoi(argv[1]));  
        return 0;  
    }  

    sbuff   = malloc(1024 * 1024 * 4 - 4);  
    rbuff   = malloc(256 * 1024 * 10 * 4);  /* 足够10000亿数据 */  
    rbuff_t = rbuff;  
    rbuff_n = 0;  

#ifdef INFO  
    s_0 = 0;  
    s_1 = 0;  
    s_2 = 0;  
    gettimeofday(&begin, NULL);  
#endif  
    while ( 0 != (n = read_input(STDIN_FILENO, sbuff, 1024 * 1024 * 4 - 4)) ) {  
#ifdef INFO  
    s_2 += n / 4;  
#endif  
        for ( j = (n / 4) / 2; j >= 0; j -- ) {  
#ifdef INFO  
    s_0 ++;  
#endif  
            max_heapify(sbuff, j);  
        }  
        for ( i = 0; i < 10; i ++ ) {  
#ifdef INFO  
    s_0 ++;  
    s_1 += 4;  
#endif  
            rbuff[rbuff_n]  = sbuff[0];  
            sbuff[0]        = sbuff[(n / 4) - 1 - i];  
            sbuff[(n / 4) - 1 - i]  = -1;  
            max_heapify(sbuff, 0);  
            rbuff_n ++;  
        }  
    }  
    for ( j = rbuff_n / 2; j >= 0; j -- ) {  
#ifdef INFO  
    s_0 ++;  
#endif  
        max_heapify(rbuff, j);  
    }  
    for ( i = 0; i < 10; i ++ ) {  
#ifdef INFO  
    s_0 ++;  
    s_1 += 4;  
#endif  
        printf("%d\n", rbuff[0]);  
        rbuff[0]    = rbuff[rbuff_n - i];  
        rbuff[rbuff_n - i]  = -1;  
        max_heapify(rbuff, 0);  
    }  
#ifdef INFO  
    gettimeofday(&end, NULL);  
#endif  

#ifdef INFO  
    fprintf(stderr, "总计[%d]个输入\n总计比较[%d]次\n总计写内存[%d]次\n总计耗时[%0.6fs]\n",   
        s_2, s_0, s_1, (end.tv_sec * 1000000 + end.tv_usec - begin.tv_sec * 1000000 - begin.tv_usec) / 1000000.0);  
#endif  

    return 0;  
}  

标签:堆排序,数字查找,C语言

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. 博主 发表 2012-09-17 08:01:00 C++陷阱:构造函数中的多态
  2. haipo 发表 2014-03-23 14:36:41 基于Mysql的流水日志记录系统
  3. vpsee 发表 2014-07-01 15:18:52 在 Django/Flask 开发服务器上使用 HTTPS
  4. 博主 发表 2014-09-01 16:00:00 C/C++中手动获取调用堆栈
  5. zeroten 发表 2012-12-22 12:57:40 约瑟夫环的数学解法
  6. 博主 发表 2014-10-18 00:00:00 C语言DNS请求解析库
  7. 博主 发表 2014-12-13 17:21:45 宏的拓展用法总结
  8. 博主 发表 2012-10-28 06:58:39 Objective-c 对象的持久化
  9. noblog 发表 2015-01-23 04:28:02 提升Java的锁性能
  10. 周兆熊 发表 2015-02-05 10:55:05 “API”之我见
  11. 博主 发表 2014-07-26 00:00:00 Nginx源码:利用C语言tricky构建函数链
  12. 博主 发表 2013-01-27 05:08:00 CCLuaObjcBridge - Lua 与 Objective-C 互操作的简单解决方案

发表评论