还是很久以前看的《编程珠玑》，开篇就是这个在特殊条件下的排序问题，当时只是粗略的看了一下，并没有真正的理解，现在又翻出了这本书，还是遇到开篇这个问题，但是这次也不知道怎么回事，一下子就理解了，细想一下，这个排序方法不难，甚至挺简单。难就难在程序上了，因为要操作到“位”这个单位上，是平常很少触及的细节，所以写程序的过程中还是遇到一些问题的。
首先上网查了一下，关于位操作的一些知识，然后问题就迎刃而解了……
源代码：
Bit类：
public class Bit
{
private int [] mBits;//用int类型来操作位。
private int mSize; //指定有多少位。
/**
* 初始化，在构造函数中指定构造多大的位。
* @param size 初始化的bit数目
*/
public Bit( int size)
{
mSize = size;
initBits();
}
/**
* 初始化整型数组
*/
private void initBits()
{
//Java中整型为32位，所以数组长度为位长度/32。
int count = ( int ) Math.ceil(mSize/32f);//Math.ceil(double a),返回大于或等于a的最小的整数值。此处的32f就等于32.0
mBits = new int [count];
clear();
}
/**
* 清空，全部置零
*/
private void clear()
{
int len = mBits.length;
for ( int index= 0 ; index<len; index++)
{
mBits[index] = 0 ;
}
}
/**
* 将指定的位，置为1
* @param pos
*/
public void set1( int pos)
{
//得到此pos在数组中的索引
int index = ( int )Math.floor(pos/32f);//Math.floor(double a)，返回小于或等于a的最大的整数值。
//System.out.println(index);
//把当前整数的第n位设置为1
mBits[index] = mBits[index] | (1 <<(31-pos%32 ));//与移位后的1进行或运算，将指定的位，置为1，注意这里的定位。
}
/**
* 将指定的位，置为1
* @param pos
*/
public void set0( int pos)
{
int index = ( int )Math.floor(pos/32f);
//把当前整数的第n位设置为0
mBits[index] = mBits[index] & ~(1 <<(31-pos% 32 ));//1移位到指定的位置后，取反，就是将0移动到指定的位置，
//然后和原数进行与运算，就将指定的位置为0了，因为0和任何数相与，都变位0
}
/**
* 获取指定位是否存在 ，若返回true，则指定的位为1，若返回false，则指定的位为0
* @param pos
* @return
*/
public boolean get( int pos)
{
int index = ( int )Math.floor(pos/32f);
return mBits[index] == (mBits[index] | 1 <<(31-pos% 32 ));//将1移动到指定的位置，和当前的数进行或运算，
//若指定的位置是1，则进行或运算后不变，若指定的位置是0，则或运算后值会改变。
//因为任何数和1相或，都变为1.
}
public int getSize()
{
return this.mSize;
}
}
BitSort类：
import java.io.*;
public class BitSort
{
/**
* 位图排序算法
* @param args
*/
private String fileIn;//读入数据的文件
private String fileOut;//写入数据的文件
public BitSort(String fileIn, String fileOut)
{
this.fileIn=fileIn;
this.fileOut=fileOut;
}
/**
* 从fileIn中读取数据，排好序后，将排好序的数据写入fileOut中。
* @throws IOException
*/
public void sort(Bit bit) throws IOException
{
FileReader fin=new FileReader(this.fileIn);//建立文件字符输入流
BufferedReader bin=new BufferedReader(fin);//建立字符缓冲输入流
FileWriter fout=new FileWriter(this.fileOut);
BufferedWriter bout=new BufferedWriter(fout);
String line="";
do{
line=bin.readLine();
if(line!=null)
{
int pos=Integer.parseInt(line);
bit.set1(pos);
}
}while(line!=null);//读取每一个数据，并且置相应的位为1，直到文件尾。
for(int j=0;j<bit.getSize();j++)//遍历位数组，输出相应的位
{
if(bit.get(j))
{
line=String.valueOf(j);
bout.write(line);
bout.newLine();//插入一个换行符
}
}
bout.close();
fout.close();
bin.close();
fin.close();
}
public static void main(String[] args) throws IOException
{
BitSort bitsort=new BitSort("in.txt","out.txt");
Bit bit=new Bit(10000000);
bitsort.sort(bit);
}
}
从中学到的东西：
1、首先是解决这个问题的思路：使用每一位来代表一个整数，这样不仅节省了空间，而且节省了时间，读取数据的过程，就是排序的过程，但前提是数据尽量紧凑，若差度太大，就很浪费空间和时间。
2、位操作：因为基本的数据类型里，没有“Bit”这个类型，所以只能在别的数据类型上加以扩充，本例是在整形的基础上进行的位操作，这样最方便。将数据操作到位，是不是需要很细心才对？其中主要是用到了位运算符，以及一些位逻辑运算，比如1和任何数的“或运算”都为1，0和任何数的“与运算”都为0，再加上移位运算，就可以随心所欲地操作某一位。
3、文件操作：这个算是对以前知识的复习吧，FileInputStream类是以字节为单位进行读取的，而FileReader类是以字符为单位进行读取的，如果想要从.txt文件中读取整数的话，还是用FileReader类比较方便，因为和它密切配合的缓冲字符流类BufferedReader有个readLine()方法，可以读取一行，然后转换成整形就可以了。
4、随机数的生成：为了练习这个算法，我得得到10000000个数据吧，一千万，本来想挺容易的，用Random类，采用for循环一千万次，就搞定了，可是我发现for循环最多只能循环到10000次，就停止了。随后写了个死循环，发现一直可以输出，我就很郁闷了，不知道这是怎么回事？望看到这篇博客的高手，给解答一下……