首页 > 代码库 > bitmap排序

bitmap排序

利用char数组模拟bitmap排序。bitmap能够用来对数组的查重,也可用来排序,时间复杂度较为可观。

public class BitmapSort {

	public static void bitmapsort(int[] num){
		if(num==null)
			return;
		int max = num[0];
		//找出最大的数。以确定位图数组的大小
		for(int i = 0 ; i<num.length ; i++){
			max = max>num[i]?

max:num[i]; } //位图数组长度 int len = max/Character.SIZE + (max%Character.SIZE==0?0:1); //创建位图数组。採用char类型就可以 char[] sort = new char[len]; //记录每一个数出现的次数 Map<Integer, Integer> map = new HashMap<Integer, Integer>(); //開始统计 for(int i = 0 ; i < num.length ; i++){ int index = num[i]/Character.SIZE; sort[index] = (char)(sort[index]|(0x01<<num[i]%Character.SIZE)); if(map.containsKey(num[i])) map.put(num[i],map.get(num[i])+1); else map.put(num[i], 1); } System.out.println(map.size()); int index = 0 ; //得出排序结果 for(int i = 0 ;i < sort.length ;i++){ for(int j = 0 ; j < Character.SIZE ; j++){ int tmp = sort[i]&(0x01<<j); if(tmp > 0){ int number = i*Character.SIZE+j; int count = map.get(number); while(count>0){ num[index++] = number; count--; }//while } }//for }//for }



bitmap排序