位图排序算法实践

　　一。算法介绍
　　排序算法是计算机专业必学的内容，教科书里介绍的像冒泡排序，插入排序，Shell排序，堆排序，快速排序等几种经典的排序算法，其中快速排序最为推荐和广为人知，其采用二分分组递归的方式，对数据巧妙而快速的排序，平均性能复杂度为NLogN，商用的代码库一般会使用快速排序（由于其最差性能复杂度为NN，像STL库里面的排序算法会结合插入排序和堆排序，使其最差性能复杂度也能达到NLogN）。但是除了这些教科书里面的算法，有没有其它的排序算法，排序算法的时间复杂度能不能突破理论上的极限NLogN呢？
　　经典的《编程珠玑》一书里对于长度在一定范围的不重复数字序列，介绍一款非常巧妙的算法位图排序，其时间复杂度达到惊人的N，很多了解通用排序算法的读者，听到的第一反应可能是大呼怎么可能！
　　且看位图排序算法的实践逻辑如下：
　　1）第一步：申请一个长度超过最大数字的数组，
　　2）第二步：遍历数字序列，以数字作为索引，将数组对应的值赋值为1。
　　3）第三步：遍历数组，打印值为1的数组索引值
　　这个算法直接打破常规思维，唤山不来，向山走去，利用空间换取时间，使算法复杂度达到了不可思议的N，简单至极而又巧妙至极！二。编程实践
　　纸上得来终觉浅，绝知此事要躬行，位图排序的实际效果到底如何，笔者开发了一个demo来验证一下，代码中使用Java的里面的位操作来实现位图存储，以节约了存储空间，另外和快排排序算法进行了性能比较，代码如下：publicstaticvoidmain（String〔〕args）｛finalintMAX1000000000；数字最大值finalintCOUNT300000000；数字个数System。out。println（排序个数：COUNT）；int〔〕intsgetRandomData（COUNT，MAX）；longstartSystem。currentTimeMillis（）；startSystem。currentTimeMillis（）；intsgetRandomData（COUNT，MAX）；startSystem。currentTimeMillis（）；quickSort（ints）；System。out。println（快速排序时间：（System。currentTimeMillis（）start））；intsgetRandomData（COUNT，MAX）；startSystem。currentTimeMillis（）；byte〔〕bytesbitmapSort（ints，MAX）；System。out。println（位图排序1时间：（System。currentTimeMillis（）start））；｝产生最大为值max，数量为count的数字privatestaticint〔〕getRandomData（intcount，intmax）｛int〔〕intsnewint〔count〕；for（inti0；icount；i）｛intran（int）（Math。random（）max）；System。out。print（ran）；ints〔i〕ran；｝returnints；｝位图排序法1，无法处理重复数据privatestaticbyte〔〕bitmapSort（int〔〕array，intmax）｛finalintlen（int）Math。ceil（max8。0）；byte〔〕bytesnewbyte〔len〕；for（inti0；iarray。length；i）｛intjarray〔i〕3；intkarray〔i〕8；bytes〔j〕setByte（bytes〔j〕，k）；｝returnbytes；｝将字节b第i位置1publicstaticBytesetByte（byteb，inti）｛b0x01i；returnb；｝快速排序paramarraypublicstaticvoidquickSort（int〔〕array）｛intlen；if（arraynull（lenarray。length）0len1）｛return；｝sort（array，0，len1）；｝快排核心算法，递归实现paramarrayparamleftparamrightpublicstaticvoidsort（int〔〕array，intleft，intright）｛if（leftright）｛return；｝base中存放基准数intbasearray〔left〕；intileft，jright；while（i！j）｛顺序很重要，先从右边开始往左找，直到找到比base值小的数while（array〔j〕baseij）｛j；｝再从左往右边找，直到找到比base值大的数while（array〔i〕baseij）｛i；｝上面的循环结束表示找到了位置或者（ij）了，交换两个数在数组中的位置if（ij）｛inttmparray〔i〕；array〔i〕array〔j〕；array〔j〕tmp；｝｝将基准数放到中间的位置（基准数归位）array〔left〕array〔i〕；array〔i〕base；递归，继续向基准的左右两边执行和上面同样的操作i的索引处为上面已确定好的基准值的位置，无需再处理sort（array，left，i1）；sort（array，i1，right）；｝
　　对于最大10亿的3亿个数字排序：运行的时间结果是：
　　快速排序：37183毫秒
　　位图排序：4019毫秒
　　比起经典的快速排序，位图排序的性能要高出9倍以上！
　　但这个算法存在一个问题，就是排序的数字序列不能有重复的数字，如何改进这个算法呢？其实很简单，只要将存储最小单元由BIT改成BYTE，相同的数字，位图数组的值加1即可，这样可以处理最多255个重复的数，应该可以满足大部分场景，改进的代码如下：位图排序法2，可处理重复最多255个数privatestaticbyte〔〕bitmapSort2（int〔〕array，intmax）｛byte〔〕resultnewbyte〔max〕；for（inti0；iarray。length；i）｛result〔array〔i〕〕；｝returnresult；｝
　　运行测试，第二种排序时间为4857毫秒，效率依然杠杠的！