Think in algorithm part.1

Efficiency

	System sort	C++/STL	C/qsort	C/bitmap
total time	89	38	12.6	10.7
computing time	79	28	2.4	0.5
MB	0.8	70	4	1.25

JAVA implementation

public class BitSortTest {  
    private static final int BITSPERWORD = 32;
    private static final int SHIFT = 5;  
    private static final int MASK = 0x1F; 
    private static final int N = 10000000;  
    private static int[] a = new int[(1 + N / BITSPERWORD)];  

    public static void main(String[] args) {  
        bitsort(new int[]{1, 100, 2, 10000, 9999, 4567, 78902});  
    }  

    public static void bitsort(int[] array) {  
        for (int i = 0; i < N; i++)  
            clr(i); 
        for (int i = 0; i < array.length; i++)  
            set(array[i]);  
        for (int i = 0; i < N; i++)  
            if (test(i))  
                System.out.println(i);  
    }  

    public static void set(int i) {  
        a[i >> SHIFT] |= (1 << (i & MASK));  
    }  

    public static void clr(int i) {  
        a[i >> SHIFT] &= ~(1 << (i & MASK));  
    }  

    public static boolean test(int i) {  
        return (a[i >> SHIFT] & (1 << (i & MASK))) == (1 << (i & MASK));  
    }  
}

---

---

blog comments powered by Disqus

Published