利用BitMap进行排序

    利用BitMap可以对某些数据进行排序，但是限制条件是必须实现知道数据的范围，而且不能重复，类似于桶排序，但是比桶排序更加节省内存。

 

     原理很简单，就是设置数组某一位的数在BitMap中对应位为1，然后遍历数组就可以得到结果。

这里以100以内的一个数组排序为例

 

例如数组：

int[] array = { 6, 2, 8, 4, 33, 23, 99, 9 };

 

则设置BitMap第6位(BitMap从第0位开始)为1，第2位为1，......

 

/**
	 * 利用BitMap进行排序;
	 * @param array
	 */
	public static void bitMapSort(int[] array){
		
		//开辟16个Byte;
		byte[] bs=new byte[16]; 
		for(int i=0;i<array.length;i++){
			//设置array[i]位为1;
			//得到Byte表中的位置;
			int pos=array[i]/8;
			//设置位;
			int index=array[i]%8;
			bs[pos]=(byte) (bs[pos]+(byte)(0x01<<(index)));
		}
		int count=0;
		int num=0;
		//遍历Byte表;
		//考虑设置数组对应位的值;
		for(int i=0;i<bs.length;i++){
			byte b=bs[i];
			for(int j=0;j<8;j++){
				byte bi=(byte) (b&(0x01<<j));
				if(bi!=0){
					num=i*8+j;
					array[count]=num;
					count++;
				}
			}
		}
		
	}

 

<!--EndFragment-->