首页 > 其他 > 详细

位图排序-《编程珠玑》

时间:2014-03-18 22:02:12      阅读:480      评论:0      收藏:0      [点我收藏+]

如题:实现位图排序,其中假设n为10 000 000,且输入文件包含1 000 000个正数;具体细节详见《编程珠玑》第一章问题

由于数据的大小问题,在这#define N 1000,即数据在1000以内的100个数据,进行排序(当然由于随机数的产生问题,有数重复,在此并未处理);

#include <stdio.h>
#include <stdlib.h>

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 1000
int a[1 + N / BITSPERWORD];

void clr(int i)
{
    a[i >> SHIFT] &= ~(1 << (i & MASK));
}

void set(int i)
{
    a[i >> SHIFT] |= (1 << (i & MASK));
}

int test(int i)
{
    return (a[i >> SHIFT] & (1 << (i & MASK)));
}

int main()
{
    FILE *fp;
    int temp;  //临时变量
    int i;

    fp = fopen("num.txt", "w");  //写入数据
    if (fp == NULL)
    {
        printf("open file failed.\n");
        return 0;
    }
    for(i = 0; i < N / 10; i++)
    {
        temp = rand() % N;
        fprintf(fp, "%d ", temp);
    }

    fclose(fp);

    for(i = 0; i < N; i++)
    {
        clr(i);
    }

    fp = fopen("num.txt", "r");  //读数据
    if (fp == NULL)
    {
        printf("open file failed.\n");
        return 0;
    }

    while(fscanf(fp, "%d", &temp) != EOF)
    {
        set(temp);
    }
    fclose(fp);

    for(i = 0; i < N; i++)  //输出排序
    {
        if(test(i))
        {
            printf("%d ", i);
        }

    }

    return 0;
}
进行排序:

bubuko.com,布布扣

对于一个内存不够的排序来说,位图排序极大的省略的空间;

当然,若是将#define N 10000000;效率及空间依然很可观;


O(∩_∩)O


位图排序-《编程珠玑》,布布扣,bubuko.com

位图排序-《编程珠玑》

原文:http://blog.csdn.net/xjm199/article/details/21476491

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!