算法——Java版位图排序

╰+哭是因爲堅強的太久メ 2021-09-27 09:32 309阅读 0赞

## 前言 ##

最近在看编程珠玑，在第一章开篇中，作者通过一次友好的对话引出了位图排序，对话大致是某位程序员问题一个问题，“怎样给一个磁盘文件排序”

## 前提 ##

输入：在一个最多包含n个正整数的文件，每个数都小于n,其中n=10^7。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。

输出：按升序排列的输入整数的列表。

约束：最多有（大约）1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化了。

## 思考 ##

1M=8\*1024\*1024位

10，000，000所需要的内存空间为10，000，000/(8\*1024\*1024)=1.2M，如果这边没有强制性的限制那么可以使用下面代码中的uniqueSort方法，如果有强制的内存限制了，那么mysort方法能够解决该问题.

作者原本的思想是用比特为来表示数字的存在，存在即把对应比特位置为1（初始化全部为0），比如集合\{1,2,4,6,7\}，对应的位图为01101011（从左往右，初始位为0），代表集合中数值的位都置为1，其他所有位都为0；这边是不考虑数值重复的，如果考虑到数值重复，那么可以给对应的位图加1（而不是像之前那样置1了）

# #

## 代码 ##

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    import java.util.Random;
    
    /**
     * Description:
     * 作者：gu.weidong(Jack)
     * date:2018年9月3日
     * ProjectName:test
     */
    public class JavaSort {
    	public static List<Integer> tempList = new ArrayList<Integer>();//ArrayList有序，按照输入顺序显示
        public static int count;
        public static long start;
        public static long end;
    
        public static void main(final String[] args) {
            Random random = new Random();
            List<Integer> firstNum = new ArrayList<Integer>();
            List<Integer> secondNum = new ArrayList<Integer>();
            List<Integer> thirdNum = new ArrayList<Integer>();
    
            for (int i = 1; i <= 10000; i++) {
                firstNum.add(i);
                secondNum.add(i);
                firstNum.add(random.nextInt(i + 1));//随机生成100000以内数字
                secondNum.add(random.nextInt(i + 1));
                thirdNum.add(random.nextInt(i + 1));
            }
            Collections.shuffle(firstNum); //洗牌，打乱数据
            Collections.shuffle(secondNum);
            Collections.shuffle(thirdNum);
    
            getStartTime();
            Collections.sort(firstNum);
            getEndTime("java sort run time  ");
    
            getStartTime();
            secondNum = uniqueSort(secondNum);
            getEndTime("uniqueSort run time ");
            
            getStartTime();
            mysort(thirdNum);
            getEndTime("mysort run time     ");
        }
    
        /**
         * 内存足够
         * Description:
         * 作者：gu.weidong(Jack)
         * date:2018年9月3日
         * @param uniqueList
         * @return List<Integer>
         */
        public static List<Integer> uniqueSort(final List<Integer> uniqueList) {
        	JavaSort.tempList.clear();
            int[] temp = new int[50001];
            for (int i = 0; i < temp.length; i++) {
                temp[i] = 0;     //各位置0
            }
            for (int i = 0; i < uniqueList.size(); i++) {
                temp[uniqueList.get(i)]++;//将对应的uniqueList中的值在数组中找到，加1（可统计重复次数），如果不想统计重复次数也可直接置1
            }
            for (int i = 0; i < temp.length; i++) {
                for (int j = temp[i]; j > 0; j--) {
                	JavaSort.tempList.add(i);//将重复数据放入
                }
            }
            return JavaSort.tempList;
        }
        
        /**
         * 内存不足的时候可以采用分割的方法，将10000/2=5000，先 处理1-5000的数据，再处理5001-10000的数据
         * Description:
         * 作者：gu.weidong(Jack)
         * date:2018年9月3日
         * @param uniqueList
         * @return List<Integer>
         */
        public static List<Integer> mysort(final List<Integer> uniqueList){
        	JavaSort.tempList.clear();
        	
        	int[] temp = new int[50001];
            for (int i = 0; i < temp.length; i++) {
                temp[i] = 0;     //各位置0
            }
            for (int i = 0; i < uniqueList.size(); i++) {
                if(uniqueList.get(i)<=5000) {
                	temp[uniqueList.get(i)]++;//将对应的uniqueList中的值在数组中找到，加1（可统计重复次数），如果不想统计重复次数也可直接置1
                }
             }
            for (int i = 0; i < temp.length; i++) {
                for (int j = temp[i]; j > 0; j--) {
                	JavaSort.tempList.add(i);//将重复数据放入
                }
            }
            for (int i = 0; i < temp.length; i++) {
                temp[i] = 0;     //各位置0
            }
            for (int i = 0; i < uniqueList.size(); i++) {
                if(uniqueList.get(i)>5000) {
                	temp[uniqueList.get(i)-5000]++;//将对应的uniqueList中的值在数组中找到，加1（可统计重复次数），如果不想统计重复次数也可直接置1
                }
             }
            for (int i = 0; i < temp.length; i++) {
                for (int j = temp[i]; j > 0; j--) {
                	JavaSort.tempList.add(i+5000);//将重复数据放入
                }
            }
        	return JavaSort.tempList;
        }
    
        public static void getStartTime() {
             start= System.nanoTime();
        }
    
        public static void getEndTime(final String s) {
            long end = System.nanoTime();
            System.out.println(s + ": " + (end - start) + "ns");
        }
    }

结果如下：

java sort run time     : 9441841ns  
uniqueSort run time : 4237650ns  
mysort run time        : 5963942ns

当数值不是特别大的时候，优势还是比较明显的

但当我这边测试数值10000000的时候结果如下：

java sort run time     : 10404464010ns  
uniqueSort run time : 16777732740ns  
mysort run time        : 2174604935ns

结局有点意外，然而通过100000以内的数据进行测试排序发现，排序结果是完全一致的，故在数据足够大的时候mysort的算法要更优于其他两种

![70][]

![70 1][]

[70]: /images/20210923/e86e9b84d9314716ba9555c14d36f12b.png
[70 1]: /images/20210923/f7815de735fa41dcb371056a3717d353.png