Borrowed "Programming Beads" from the library before going to the holiday, and the authors will be shocked, and the author has solved a realistic problem in order to sort a chart:
There are 30 million mobile phone numbers, 1M memory, abundance, need to order this 30 million calls
Taking this author to lead the bitmap:
The bitmap sorting refers to the number of sets that require sorting (after "1" or "0" in each bit is indicated by "1" or "0" in each bit. For example, the set is {2, 7, 4, 9, 1, 10}, generate a 10-bit string, and the positions 2, 7, 4, 9, 1, 10 are "1", and the remaining position is "0" , Then after all the bits in the string are set, the sort is automatically completed (because the subscript is ordered): 1101001011
The code sorted by bitmap is as follows:
Public void bitmapsort (int [] set) {
INT MAX = Max (SET);
Int [] array = new int [max];
For (int i = 0; i Array [i] = 0; For (int i = 0; i Array [set [i]] = 1; For (int i = 0; i IF (array [i] == 1) System.out.println (i ""); } } Private Int Max (int [] set) { // Return the maxium integer of the set } It can be seen that the time complexity of bitmap sort is O (n), which is fast than the general sort, but it is in space change time (requires a N-bit string), and some restrictions, such as sorting a collection The size is preferably known, and the maximum number of elements in the collection must be known, preferably wicking data (not the space is wasted).
