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

```
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

震惊