当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

编程珠玑-第一章-位图排序

发表于: 2012-07-05   作者:bylijinnan   来源:转载   浏览:
摘要: import java.io.BufferedWriter; import java.io.File; import java.io.FileWriter; import java.io.IOException; import java.io.Writer; import java.util.Random; public class BitMapSearch {

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;
import java.util.Random;

public class BitMapSearch {

    /**
     * 编程珠玑 第一章 位图排序
     */

    public static final int SHIFT = 5; // 2^5=32=Integer.SIZE,不直接写32的原因是为了用移位代替除法
    public static final int MASK = 0x1F; // 31=(0001,1111)
    public static final Random random = new Random();

    public static void main(String[] args) {
        BitMapSearch test = new BitMapSearch();
        int length = 10;
        int max = 99;
        int[] array = test.generateOriginArray(length, max);
        
        //输出到文件,方便观察测试结果
        test.outputArray(array, "d:/tmp/beforeSort.txt");
        int[] sortedArray = test.sort(array, max);
        test.outputArray(sortedArray, "d:/tmp/afterSort.txt");
        System.out.println("is sorted ? " + test.isSorted(sortedArray));
    }

    public int[] sort(int[] x, int max) {

        if (x == null || x.length < 2) {
            return x;
        }

        int len = x.length;
        
        //分块。一块(h[i]), 32bit,可以代表32个数
        int[] h = new int[1 + (max / 32)];
        for (int i = 0; i < len; i++) {
            set(h, x[i]);   // 将对应的bit置为1
        }

        int[] y = new int[len];
        for (int j = 0, i = 1; i < max; i++) {
            if (exist(h, i)) {  // 检查对应的bit位上是否为1
                y[j++] = i;
            }
        }
        return y;
    }

    public void set(int[] h, int i) {
        h[i >> SHIFT] |= (1 << (i & MASK)); // h[i>>SHIFT]这里面的移位操作达到分块的效果
    }

    public boolean exist(int[] h, int i) {
        return ((h[i >> SHIFT]) & (1 << (i & MASK))) != 0;
    }

    /*
    //打乱数组
    public void shuffle(int[] x) {
        int L = x.length;
        for (int i = L; i > 1; i--) {
            int j = random.nextInt(i);
            swap(x, i - 1, j);
        }
    }

    // has not been used in this case
    public void clear(int[] h, int i) {
        h[i >> SHIFT] &= ~(1 << (i & MASK));
    }
    */
    
    public void swap(int[] x, int i, int j) {
        int tmp = x[i];
        x[i] = x[j];
        x[j] = tmp;
    }
    

    /**
     * 随机生成指定长度的正整数数组,没有重复
     * @param length 数组长度
     * @param max 数组元素的最大值
     * @return
     */
    public int[] generateOriginArray(int length, int max) {
        
        //1~max
        int[] sample = new int[max];
        for (int i = 0; i < max; i++) {
            sample[i] = i + 1;
        }
        
        //随机选出length个元素
        int[] array = new int[length];
        for (int i = 0; i < length; i++) {
            int pos = random.nextInt(max);
            array[i] = sample[pos];
            sample[pos] = sample[max - 1];
            max--;
        }
        
        return array;
    }
    

    public void outputArray(int[] array, String filePath) {
        if (array == null || array.length == 0) {
            return;
        }

        File file = new File(filePath);
        if (file.exists()) {
            file.delete();
        }
        
        //StringBuilder的长度太大,会造成溢出,跟JVM的内存大小有关。为避免这种情况,达到指定长度后就输出
        int fixedLength = 1000;
        StringBuilder sb = new StringBuilder(fixedLength);
        for (int i = 0, len = array.length; i < len; i++) {
            sb.append(array[i] + "\n");
            if (sb.length() == fixedLength || (i == len - 1)) {
                this.appendStringToFile(sb.toString(), filePath);
                sb = new StringBuilder(fixedLength);
            }
        }
    }
    
    public boolean isSorted(int[] array) {
        boolean result = true;
        for (int i = 0, len = array.length; i < len -1; i++) {
            if (array[i] > array[i + 1]) {
                result = false;
                break;
            }
        }
        return result;
    }

    public void appendStringToFile(String str, String filePath) {
        Writer bw = null;
        FileWriter fileWriter = null;
        try {
            fileWriter = new FileWriter(filePath, true);
            bw = new BufferedWriter(fileWriter);
            bw.write(str);
        } catch (Exception e) {
            System.out.println("append to file failed");
            e.printStackTrace();
        } finally {
            try {
                bw.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
}

编程珠玑-第一章-位图排序

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
位图排序是一种效率极高(复杂度可达O(n))并且很节省空间的一种排序方法,但是这种排序方法对输入的
问题: 输入:给出至多10,000,000个正整数的序列 特征:每个数都小于10,000,000、数据不重复 且 数
快速排序(编程珠玑) 编程珠玑第二版快速排序 1 qsort4( 0 , n - 1 ); 2 isort3(); 3 4 void qsort
前言: 这本书也是看了别人的博客推荐过来的一本好书,先读了文章的前言,建议我们的学习的速度不要
一步一步优化的快速排序,速度比插入排序快很多,而且可以很方便的引入随机算法来避免最差情况。 #i
转载。。。。 编程珠玑开篇--磁盘文件排序问题 输入: 所输入的文件,至多包含n个正整数,每个正整数都
编程珠玑开篇--磁盘文件排序问题——转自http://blog.csdn.net/fisher_jiang/ 输入: 所输入的文件,
写在前面的 2012年3月25日买下《编程珠玑》,很期待但不知道它能给我带来什么! 编程珠玑,字字珠玑
位图排序是一种效率极高(复杂度可达O(n))并且很节省空间的一种排序方法,但是这种排序方法对输入的
一.位图排序的应用: 1.给40亿个不重复的unsigned int的整数,没有排过序,然后再给一个数,如果快
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号