位图排序: 适合数量较多的整数集合排序。
原理: 定义位组,如果整数i存在,则将位组的第i位置为1,以记录其存在。然后位组遍历,确定排序。
Code:
1 import java.io.*;
2 import java.util.*;
3 public class Main {
4
5
6 public static void main(String[] argc) throws IOException{
7
8 Main test = new Main();
9 String largeFileName = "d:\\File_test\\old.txt";
10 String destlargeFileName = "d:\\File_test\\new.txt";
11 test.perform(largeFileName, 100, destlargeFileName,true);
12 }
13
14
15 private BitSet bits;
16 public void perform( String largeFileName,int total, String destLargeFileName,boolean asc) throws IOException {
17 System.out.println("BitmapSort Started.");
18 long start = System.currentTimeMillis();
19 bits = new BitSet(total);
20 FileWriter fw=new FileWriter(new File(destLargeFileName));
21 BufferedWriter largeOut=new BufferedWriter(fw);
22 File fr = new File(largeFileName);
23 BufferedReader largeIn = new BufferedReader(new FileReader(fr));
24
25 // OutputStreamWriter osw=new OutputStreamWriter(fos, "UTF-8");
26 //BufferedWriter bw=new BufferedWriter(osw);
27 Integer data;
28 int off = 0;
29 try {
30 while (true) {
31 String Data = largeIn.readLine();
32 if (Data == null)
33 break;
34 data = Integer.parseInt(Data);
35 int v = data;
36 set(v);
37 off++;
38 }
39 largeIn.close();
40 int size = bits.size();
41 System.out.println(String.format("lines : %d ,bits : %d", off, size));
42 if(asc) {
43 for (int i = 0; i < size; i++) {
44 if (get(i)) {
45 largeOut.write(String.valueOf(i)+"\n");
46 largeOut.write("\t\n");
47 }
48 }
49 }
50 largeOut.close();
51 long stop = System.currentTimeMillis();
52 long elapsed = stop - start;
53 System.out.println(String.format("BitmapSort Completed.elapsed : %dms",elapsed));
54 }
55 finally {
56 largeIn.close();
57 largeOut.close();
58 }
59 }
60
61 private void set(int i) {
62 bits.set(i);
63 }
64 private boolean get(int v) {
65 return bits.get(v);
66 }
67 }