欢迎来到入门教程网!

C语言

当前位置:主页 > 软件编程 > C语言 >

C++实现位图排序实例

来源:本站原创|时间:2020-01-10|栏目:C语言|点击:

在《编程珠玑》一书里提到了一种算法导论里没有提到过的位图排序方法,这种排序方法是通过牺牲空间效率来追求时间效率(线性时间)以达到时间-空间折中与双赢的目的。本文以实例形式简单讲一下位图排序思想。

一、问题描述

     1.输入:一个至多包含1千万个非负整数的文件

     2.特征:①每个数都是小于10000000的非负整数;②没有重复的数字;③数据之间不存在关联关系。

     3.约束:①最多1MB的内存空间可用;②磁盘空间充足;③运行时间最多几分钟,最好是线性时间。
    
     4.输出:按升序排列的整数序列。

二、位图排序思想

由于待排序的数据记录较多,我们单纯地使用常见的排序方法时间效率较低,运行时间会很长。而且内存空间有限(限制为1MB左右),所以我们不能同时把所有整数读入内存(如果每个整数使用7个字节来存储,那么1MB内存空间只能存大约143000个数字)。当然我们可以多次读取输入文件,多次排序,但是更好的方案是使用位图排序,可以使用有限的1MB内存空间并只进行一趟排序。

1.根据待排序集合中最大的数,开辟一个位数组,用来表示待排序集合中的整数;

2.待排序集合中的数字在位数组中的对应位置置1,其他的置0;

例如,待排序集合{1,2,3,5,8,13}可以表示为:0-1-1-1-0-1-0-0-1-0-0-0-0-1

这样排序过程自然可以分为三步:

第一步:将所有的位都置为0;

第二步:通过读入文件中的每个整数,将每个对应的位都置为1;

第三步:检验每一位,如果该位为1,输出对应的整数。

注意:位图排序是使用一个二进制位而不是一个整数来表示0或1,这样可以大大地减少所需要的内存空间。使用位图排序的前提是要知道待排序序列中的最大数。位图排序的缺点是有些数没有出现过,仍要为其保留一个位。故位图排序比较适合关键字密集的序列,例如一个城市的电话号码。

伪代码如下:

/*Phase 1: initialize set to empty*/ 
  for i = [0, n) 
    bit[i] = 0 
/*Phase 2: insert present elements into the set*/ 
  for each i in the input file 
    bit[i] = 1 
/*Phase 3: write sorted output*/ 
  for i = [0, n) 
    if bit[i] == 1 
      write i on the output file 

性能:时间复杂度可达O(n),1MB包含8*1024*1024个位,所需内存10000000/(8*1024*1024)=1.20MB,如果不是严格限制的话可以看做基本符合要求。

三、位图排序实现

位图排序时,我们需要考虑:给出一个数,如何找到其对应位图的位置,方法就是首先找到该数对应的字节,然后在找到该数对应的位。例如:

unsigned char bitmap[2]; 
/* 可以表示16个数,即0~15 */ 

一个字节有八位,5表示第0个字节的第5位上;14表示第1个字节的第6个位上。

在这里为了简化位处理,我们使用C++标准库的bitset容器。bitset是C++提供的一种位集合的数据结构,它让我们可以像使用数组一样使用位,可以访问指定下标的bit位。和其他容器一样,bitset也是一个模板类。具体的bitset方法可以查看std::bitset reference。

下面我们使用bitset容器进行位图排序:

/************************************************************************* 
  > File Name: BitSort.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<bitset> 
#include<iostream> 
using namespace std; 
 
#define MAX 20 
 
int main() 
{ 
  int arr[10] = {5,1,2,13,7,10,0,20,16,9}; 
 
  bitset<MAX+1> bit; 
   
  /* 将对应位置置1 */ 
  for(int i=0; i<10; ++i) 
  { 
    bit.set(arr[i]); 
    /* bit.set(n)表示将第n位置1 */ 
  } 
 
  /* 输出排序结果 */ 
  for(int i=0; i<MAX+1; ++i) 
  { 
    /* bit.test(n)判断第n位是否为1 */ 
    if(bit.test(i)) 
    { 
      cout << i << " "; 
    } 
  } 
  cout << endl; 
} 

输出结果:0 1 2 5 7 9 10 13 16 20

上一篇:C++中new与delete、malloc与free应用分析

栏    目:C语言

下一篇:Linux网络编程之UDP Socket程序示例

本文标题:C++实现位图排序实例

本文地址:https://www.xiuzhanwang.com/a1/Cyuyan/3495.html

网页制作CMS教程网络编程软件编程脚本语言数据库服务器

如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

联系QQ:835971066 | 邮箱:835971066#qq.com(#换成@)

Copyright © 2002-2020 脚本教程网 版权所有