岂今我看过的最强的排序算法

时间:2010-03-11 11:37:16  来源:第二电脑网  作者:第二电脑网

  第二电脑网导读:ine N 10000000    8int a[1 + N/BITSPERWORD];    9   10void set(int i){   11 a[i >> SHIFT] |= (1<<(i & MASK));   12}   13   14void clr(int i){   15 a[i >> SHIFT] &= ~(1<<(i & MASK));  &n...
  正文:1//位图排序法,时空高效的至高境界
   2#include <cstdio>
   3
   4#define BITSPERword 32
   5#define SHIFT 5
   6#define MASK 0x1F
   7#define N 10000000
   8int a[1 + N/BITSPERWORD];
   9
  10void set(int i){
  11 a[i >> SHIFT] |= (1<<(i & MASK));
  12}
  13
  14void clr(int i){
  15 a[i >> SHIFT] &= ~(1<<(i & MASK));
  16}
  17
  18int test(int i){
  19 return a[i >> SHIFT] & (1<<(i & MASK));
  20}
  21
  22int main(void) {
  23 int i;
  24 for (i = 0; i < N; i++) {
  25 clr(i);
  26 }
  27 //while (scanf("%d", &i) != EOF) {
  28 // set(i);
  29 //}
  30 for (int j = 0; j < 3; j++) { //供简单的正确性测试
  31 scanf("%d", &i); //注意,输入的数不能重复
  32 set(i); //否则当只输入一次
  33 }
  34 for (i = 0; i < N; i++) {
  35 if (test(i))
  36 printf("%dn", i);
  37 }
  38 return 0;
  39}
  为什么说这个算法时空效率达到及致呢?我们对100万个不重复的正整数(1000000以内)的文件进行测试:
  
   系统排序 C++/STL.set C/qsort C/位图
  总时间(s) 89 38 12.6 10.7
  计算时间(s) 79 28 2.4 0.5
  内存使用(MB) 0.8 70 4 1.25
  (本测试数据是在较旧的计算机上测试的,但还是体现性能的差距)
    第一行是总时间,第二行的计算时间是总时间减去数据读取耗时10.2秒。虽然通用C++程序使用内存和CPU时间是专用C程序(C/位图)的50倍,但是它的使用仅需要一半的代码,并能很容易扩展到其他问题上,这也是专用C程序最大的缺点吧。
    下文回复还有网友提供的Bitmap排序的C#版,我还没有进行性能测试,估计性能也是很好的,而且那样的程序扩展性显然强很多。 《岂今我看过的最强的排序算法》由第二电脑网原创提供,转载请注明:http://www.002pc.com/master/College/Programming/aspnet/13192.html


关键字:

关于《岂今我看过的最强的排序算法》文章的评论

站内搜索: 高级搜索

热门搜索: Windows style 系统 tr IP QQ CPU 安装 function 注册 if td