Chinaunix首页 | 论坛 | 博客
  • 博客访问: 586479
  • 博文数量: 201
  • 博客积分: 3076
  • 博客等级: 中校
  • 技术积分: 2333
  • 用 户 组: 普通用户
  • 注册时间: 2009-08-02 19:44
文章分类

全部博文(201)

文章存档

2010年(118)

2009年(83)

我的朋友

分类:

2010-05-23 00:31:57

http://hi.baidu.com/xwf_like/blog/item/0fd69f3fa29f5ff2828b13a5.html


对于排序问题,想必大家都非常熟悉。而且,应该都知道基于比较的排序方法的时间复杂度的下界是 O(n*logn)。尽管又出现了基数排序,使得排序类算法的时间复杂度改进到 O(d*n),但是基数排序方法实现起来还是比较麻烦的。下面这种排序方法的时间复杂度可以认为是 O(n),但是和基数排序方法相比,它的实现非常简单。

       为了介绍这种方法,需要对输入数据作如下假定:(1)都是非负整数,(2)每个整数最多出现一次,(3)最大整数小于 n。

       这种方法采用哈希函数的思想,用一个整型数组 array[n] 来实现对输入数据的排序工作。具体点就是:(1)初始化,将数组的每个元素清 0;(2)插入数据并实现排序,对于输入数据 i,置 array[i] 为 1; (3)输出排序结果,如果 array[i] 为 1,就输出整数 i。

       这种方法的优点是,可以边输入数据边进行排序,这对于实时处理来说是非常合适的。当然它的缺点也是明显的,不能处理负数和小数,当输入数据的范围很大时, 数组 array 会很大,要占据非常大的内存空间,这样对它的初始化就是一件比较费时的操作。

       可能有人已经想到用 short int 类型数组,或者 bool 类型数组来实现算法,以达到减少所需内存空间的目的。这些想法的关键就是用较少的内存,或者说二进制位来标识每个数据。那么在计算机中标识每个数据最少需 要多少位呢?1 位!

       在实现这种方法之前,先看一下它的内存需求和以前相比由多少改进。如果我们用整型数组来实现排序,那么标识一个数据需要 32 位;如果用 bool 类型数组来实现,需要 8 位;最后,如果用下面要说的位向量来实现的话,标识一个数据只需 1 位。

       所谓位向量就是由若干二进制位组成的一个向量。

       而我们熟知的 C++/C 中没有对应一个二进制位的数据类型,因此,要实现位向量,需要借助于位操作。

       下面是我实现的代码:

#ifndef _INTSETBITVEC_
#define _INTSETBITVEC_
class IntSetBitVec
{
public:
IntSetBitVec(int maxval)
{
   hi = maxval;
   x = new int[1 + hi / BITSPERWORD];
   for(int i = 0; i < hi; i++)
   {
    clr(i);
   }
   n = 0;
}
~IntSetBitVec()
{
   n = 0;
   delete [] x;
}
int size()              // 返回实际输入数据的个数
{
   return n;
}
void insert(int t)      // 插入数据,实现排序功能
{
   if(test(t))
    return;
   set(t);
   n++;
}
void report(int *v)     // 将排序后的数据存储到指针 v 所指的整型数组中
{
   int j = 0;
   for(int i = 0; i < hi; i++)
   {
    if(test(i))
     v[j++] = i;
   }
}
private:
enum
{                                     // 这些参数仅适用于整型变量为 32 位的机器. 如果整型变量的位数为其他值
   BITSPERWORD = 32,   // 如 64, 则这些参数应设置为:
   SHIFT = 5,                     // BITSPERWORD = 64
   MASK = 0x1F                // SHIFT = 6
};                                   // MASK = 0x3F

void set(int i)         // 将位向量的第 i 位置 1
{
   x[i >> SHIFT] |= (1 << (i & MASK));
}
void clr(int i)         // 将位向量的第 i 位清 0
{
   x[i >> SHIFT] &= ~(1 << (i & MASK));
}
int test(int i)         // 检测位向量第 i 位是否为 1
{
   return x[i >> SHIFT] & (1 << (i & MASK));
}

int n, hi, *x;
};
#endif

阅读(1172) | 评论(0) | 转发(0) |
0

上一篇:因子个数

下一篇:elf 格式分析

给主人留下些什么吧!~~