『プログラミング珠玉』におけるビットスイッチによるソート方法を記録する
2075 ワード
プログラムは,1000万から1億までの乱数1000万個を自動的に生成してファイルに書き込み,これらの数を小さい順に新しいファイルに書き込むことを実現する.
コア思想:大きな配列で乱数の出現回数を記録し、この基数器のシーケンス番号を直接出力することがソート結果である.
コア思想:大きな配列で乱数の出現回数を記録し、この基数器のシーケンス番号を直接出力することがソート結果である.
private static final int SIZE = 10000000;//
private static final int START = 10000000;//
private static final int END = 89999999;//
private static final String DIR = "e:/test/";
public static void main(String[] args) throws Exception{
long time = System.currentTimeMillis();
createTestData();
System.out.println(" :"+(System.currentTimeMillis() - time));
time = System.currentTimeMillis();
sort();
System.out.println(" :"+(System.currentTimeMillis() - time));
System.out.println(" !");
}
private static void sort()throws Exception{
System.out.println(" ...");
int[] record = new int[END+1];
for(int i = 0;i<record.length;i++){
record[i] = 0;
}
File file = new File(DIR+"test.txt");
BufferedReader br = new BufferedReader(new FileReader(file));
String line;
while((line = br.readLine())!=null){
record[Integer.parseInt(line) - START] += 1;
}
br.close();
System.out.println(" ...");
File file2 = new File(DIR+"test-result.txt");
if(!file.exists()){
file.createNewFile();
}
BufferedWriter bw = new BufferedWriter(new FileWriter(file2,true));
int i = START;
for(int r : record){
if(r>=1){
for(int j = r;j>0;j--){
bw.write(i+(r>1?" <---":""));
bw.newLine();
}
}
i++;
//System.out.println("i="+i);
}
bw.close();
}
private static void createTestData()throws Exception{
Random r = new Random();
File file = new File(DIR+"test.txt");
if(!file.exists()){
file.createNewFile();
}
System.out.println(" ...");
BufferedWriter bw = new BufferedWriter(new FileWriter(file,true));
for(int i = 0;i<SIZE;i++){
bw.write(START+r.nextInt(END)+"");
bw.newLine();
//System.out.println("i="+i);
}
bw.close();
}