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

赞 (0)

相关推荐

  • C++实现图形界面时钟表盘代码

    本文实例讲述了C++实现图形界面时钟表盘代码,分享给大家供大家参考. 具体实现代码如下: 复制代码 代码如下: //POINT的数组可以这么用      POINT pt[]={          0, 450,          225,390,          390,225,          450,0,          390,-225,          225,-390,          0,-450,          -225,-390,          -390,-2

  • C++输出上三角/下三角/菱形/杨辉三角形(实现代码)

    1.输出上三角形第一行1个星,第二行3个星,第三行5个星,第四行7个星,第五行9个星.分析:三角形的形状由输出的空白和星组成,通过分析每一行输出几个空格,几个星,就可完成输出三角形的工作. 复制代码 代码如下: #include<iostream>using namespace std;int main(){ int i=0,j=0; for(i=1;i<=5;i++){//控制行数      for(j=1;j<=(5-i);j++){      cout<<&quo

  • C++输出斐波那契数列的两种实现方法

    定义: 斐波那契数列指的是这样一个数列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...这个数列从第三项开始,每一项都等于前两项之和. 以输出斐波那契数列的前20项为例: 方法一:比较标准的做法,是借助第三个变量实现的. 复制代码 代码如下: #include<iostream>  using namespace std;int main(){    int f1=0,f2=1,t,n=1;    cout<<"数列第1个

  • C++ 设置透明背景图片

    背景: 有两个图片,一个是目标背景图片, 一个是带有自身背景色彩的彩色图片 先将这彩色图片绘制到目标背景图片中, 这一步通过BITBLT就可实现.   但实现后的效果是: 目标图片上,绘制上去的彩色图片带有其本身的背景. 问题就来了, 我们想将彩色图片本身的背景去掉,应该如何解决? 解决方法: 使用API函数:TransparentBlt   此函数将原DC中的图片绘制到目标DC中,并同时设置原图形在目标图形上的透明色. BOOL TransparentBlt( HDC hdcDest, //

  • C++简单输出钻石菱形图效果

    C++简单输出钻石菱形图效果

    本文实例讲述了C++简单输出钻石菱形图效果的方法.分享给大家供大家参考,具体如下: /* * 作 者: 刘同宾 * 完成日期:2012 年 11 月 25 日 * 版 本 号:v1.0 * 输入描述: * 问题描述: 设计和输出钻石图形. * 程序输出: * 问题分析:略 * 算法设计:略 */ #include<iostream> using namespace std; int main() { char a[][5]={{' ',' ','*'},{' ','*',' ','*'},{'

  • c++输出斐波那契数列示例分享

    复制代码 代码如下: #include "stdio.h" int Feibo(int Num){if(Num == 1 || Num == 2){return 1;}else{return Feibo(Num - 1) + Feibo(Num - 2);}} void main(){int NumIn,i;scanf("%d", &NumIn);for(i=1;i<NumIn;i++){printf("%d ",Feibo(i))

  • C++将CBitmap类中的图像保存到文件的方法

    本文实例讲述了C++将CBitmap类中的图像保存到文件的方法.分享给大家供大家参考.具体实现方法如下: 使用下面的代码,可以把CBitmap类中的图像保存到图像文件中.支持格式:BMP.JPG.GIF和PNG. void SaveBitmap(CString strFilePath, CBitmap Bitmap) { if ( Bitmap.m_hObject ) { CImage imgTemp; // CImage是MFC中的类. imgTemp.Attach(Bitmap.operat

  • C++中基本的输入输出函数使用指南

    在C语言中是用printf函数进行输出,用scanf函数进行输入的.C++保留了C语言的这一用法. scanf函数一般格式是: scanf(格式控制, 输出表列) printf函数的一般格式是     scanf(格式控制, 输出表列) scanf(格式控制, 输出表列) [例]用scanf和printf函数进行输入和输出. #include <iostream> using namespace std; int main( ) { int a; float b; char c; scanf(

  • C++实现二维图形的傅里叶变换

    本文实例讲述了C++实现二维图形的傅里叶变换的方法.有一定的借鉴价值.分享给大家供大家参考. 具体代码如下: // Fourier.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "stdio.h" #include "math.h" #include <cv.h> #include <highg

  • C++输入一个字符串,把其中的字符按照逆序输出的两种方法解析

    用字符数组方法:基本思路是,先判断字符的结束标志'\0',然后从该位置向前输出.实现代码: 复制代码 代码如下: #include<iostream>using namespace std;int main(){ char a[50]; cout<<"please input a string:"; cin>>a; int i=0,k=0; while(i<50){        if(a[i]=='\0'){         k=i;    

  • CISBitmap派生的VC++位图透明类实例

    本文所述为一个由CISBitmap派生的VC++位图透明类,可以方便实现BMP图像的透明处理,主要包含两个文件,使用时主需要将其引入到你的C++工程中即可,具体的类代码如下: CISBitmap.cpp文件代码如下: #include <stdafx.h> #include "CISBitmap.h" #ifdef _DEBUG #undef THIS_FILE static char THIS_FILE[]=__FILE__; #define new DEBUG_NEW

随机推荐