位图排序算法实践

　　一.算法介绍
　　排序算法是计算机专业必学的内容，教科书里介绍的像冒泡排序，插入排序，Shell排序，堆排序，快速排序等几种经典的排序算法，其中快速排序最为推荐和广为人知，其采用二分分组递归的方式，对数据巧妙而快速的排序，平均性能复杂度为N*LogN，商用的代码库一般会使用快速排序（由于其最差性能复杂度为N*N，像STL库里面的排序算法会结合插入排序和堆排序，使其最差性能复杂度也能达到NLogN）。但是除了这些教科书里面的算法，有没有其它的排序算法，排序算法的时间复杂度能不能突破理论上的极限N*LogN呢？
　　经典的《编程珠玑》一书里对于长度在一定范围的不重复数字序列，介绍一款非常巧妙的算法 -位图排序 ，其时间复杂度达到惊人的 N， 很多了解通用排序算法的读者，听到的第一反应可能是大呼＂怎么可能！＂
　　且看位图排序算法的实践逻辑如下：
　　1）第一步：申请一个长度超过最大数字的数组，
　　2）第二步：遍历数字序列，以数字作为索引，将数组对应的值赋值为1.
　　3）第三步：遍历数组，打印值为1的数组索引值
　　这个算法直接打破常规思维，唤山不来，向山走去，利用空间换取时间，使算法复杂度达到了不可思议的 N， 简单至极而又巧妙至极！ 二.编程实践
　　＂纸上得来终觉浅，绝知此事要躬行＂，位图排序的实际效果到底如何，笔者开发了一个demo来验证一下，代码中使用Java的里面的位操作来实现位图存储，以节约了存储空间，另外和快排排序算法进行了性能比较，代码如下： public static void main(String[] args) {     final int MAX = 1000000000; //数字最大值     final int COUNT = 300000000;//数字个数          System.out.println(＂排序个数:＂ + COUNT);     int[] ints = getRandomData(COUNT, MAX);     long start = System.currentTimeMillis();     start = System.currentTimeMillis();     ints = getRandomData(COUNT, MAX);     start = System.currentTimeMillis();     quickSort(ints);     System.out.println(＂快速排序时间:＂ + (System.currentTimeMillis() - start));          ints = getRandomData(COUNT, MAX);     start = System.currentTimeMillis();     byte[] bytes = bitmapSort(ints, MAX);     System.out.println(＂位图排序1时间:＂ + (System.currentTimeMillis() - start)); }  // 产生最大为值max，数量为count的数字 private static int[] getRandomData(int count, int max) {     int[] ints = new int[count];     for (int i = 0; i < count; i++) {         int ran = (int) (Math.random() * max);         //System.out.print(ran + ＂ ＂);         ints[i] = ran;     }     return ints; }  // 位图排序法1，无法处理重复数据 private static byte[] bitmapSort(int[] array, int max) {     final int len = (int) Math.ceil(max / 8.0);     byte[] bytes = new byte[len];     for (int i = 0; i < array.length; i++) {         int j = array[i] >> 3;         int k = array[i] % 8;         bytes[j] = setByte(bytes[j], k);     }     return bytes; }  // 将字节b第i位置1 public static Byte setByte(byte b, int i) {     b |= 0x01 << i;     return b; }  /**  * 快速排序  *  * @param array  */ public static void quickSort(int[] array) {     int len;     if (array == null             || (len = array.length) == 0             || len == 1) {         return;     }     sort(array, 0, len - 1); }  /**  * 快排核心算法，递归实现  *  * @param array  * @param left  * @param right  */ public static void sort(int[] array, int left, int right) {     if (left > right) {         return;     }     // base中存放基准数     int base = array[left];     int i = left, j = right;     while (i != j) {         // 顺序很重要，先从右边开始往左找，直到找到比base值小的数         while (array[j] >= base && i < j) {             j--;         }          // 再从左往右边找，直到找到比base值大的数         while (array[i] <= base && i < j) {             i++;         }          // 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置         if (i < j) {             int tmp = array[i];             array[i] = array[j];             array[j] = tmp;         }     }      // 将基准数放到中间的位置（基准数归位）     array[left] = array[i];     array[i] = base;      // 递归，继续向基准的左右两边执行和上面同样的操作     // i的索引处为上面已确定好的基准值的位置，无需再处理     sort(array, left, i - 1);     sort(array, i + 1, right); }
　　对于最大10亿的3亿个数字排序：运行的时间结果是：
　　快速排序：37183毫秒
　　位图排序：4019毫秒
　　比起经典的快速排序，位图排序的性能要高出 9倍以上！
　　但这个算法存在一个问题，就是排序的数字序列不能有重复的数字，如何改进这个算法呢？其实很简单，只要将存储最小单元由BIT改成BYTE，相同的数字，位图数组的值加1即可，这样可以处理最多255个重复的数，应该可以满足大部分场景，改进的代码如下： // 位图排序法2，可处理重复最多255个数     private static byte[] bitmapSort2(int[] array, int max) {         byte[] result = new byte[max];         for (int i = 0; i < array.length; i++) {             result[array[i]]++;         }         return result;     }
　　运行测试，第二种排序时间为4857毫秒，效率依然杠杠的！