如题:实现位图排序,其中假设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; }进行排序:
对于一个内存不够的排序来说,位图排序极大的省略的空间;
当然,若是将#define N 10000000;效率及空间依然很可观;
O(∩_∩)O
原文:http://blog.csdn.net/xjm199/article/details/21476491