10億個字符串的排序問題

一、問題描述

有一個大文件，里面有十億個字符串，亂序的，要求將這些字符串以字典的順序排好序

二、解決思路

? ? 將大文件切割成小文件，每個小文件內歸并排序；

? ? 對所有的小文件進行歸并排序——多重歸并排序

三、解決方案

3.1?模擬產生10億個隨機字符

public static void generateDate() throws IOException {BufferedWriter writer = new BufferedWriter(new FileWriter(ORIGINALPATH));Random random = new Random();StringBuffer buffer = new StringBuffer("0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ");int range = buffer.length();int length = 1;for (int i = 0; i < BIGDATALENGTH; i++) {StringBuffer sb = new StringBuffer();length = random.nextInt(20)+1;//System.out.println("length--->"+length);for (int j = 0; j < length; j++) {//System.out.println("j--->"+j);sb.append(buffer.charAt(random.nextInt(range)));}System.out.println("sb---->"+sb);writer.write(sb.toString() + "
");}writer.close();
}

3.2?對大文件進行切割

/**

}

/*** 將原始數據分成幾塊 并排序 再保存到臨時文件* @throws IOException*/
public static void splitData() throws IOException {@SuppressWarnings("resource")BufferedReader br = new BufferedReader(new FileReader(ORIGINALPATH));tempFiles = new File[BIGDATALENGTH / TEMPFILELENGTH];//將會產生的臨時文件列表for (int i = 0; i < tempFiles.length; i++) {tempFiles[i] = new File(TEMPFILEPATH + "TempFile" + i + ".txt");BufferedWriter writer = new BufferedWriter(new FileWriter(tempFiles[i]));HashMap<Integer,String> hashMap = new HashMap<Integer,String>();//未排序//每次讀出TEMPFILELENGTH個文件 保存到smallLine中for (int j = 1; j <= TEMPFILELENGTH; j++) {String text = null;if ((text = br.readLine()) != null) {hashMap.put(j, text);}}hashMap = MergeSort.sort(hashMap);for(int k=1; k<=TEMPFILELENGTH; k++){writer.write(String.valueOf(hashMap.get(k))+ System.getProperty("line.separator"));
//System.getProperty("line.separator")相當于}writer.close();}
}

3.3?對小文件進行遞歸歸并

/*** 多路歸并排序* @param files* @throws IOException*/
public static void multiWaysMergeSort(String[] files) throws IOException {System.out.println("歸并文件-----第 "+mergeSortCount+" 次-----");//當最后只有一個文件的時候 數據已經排序成功 直接復制保存到結果文件if (files.length == 1) {String lastFilePath = LASTFILEPATH + LASTFILENAME;copyFile(files[0], lastFilePath, false);//deleteFile(files[0]);return;}for (int i = 0; i < files.length; i+=2) {
//開始合并兩個相鄰的文件 所以一次跳兩個if (i == files.length - 1) {
//這時候已經只剩下最后一個文件了 不需要合并 本趟歸并結束renameFile(files[i], i);break;}//將br1 和 br2 寫入到WriteBufferedReader br1 = new BufferedReader(new FileReader(files[i]));BufferedReader br2 = new BufferedReader(new FileReader(files[i + 1]));BufferedWriter writer = new BufferedWriter(new FileWriter(TEMPFILEPATH + "last_" + mergeSortCount + "_" + i + ".txt"));String s1 = br1.readLine();String s2 = br2.readLine();while (s1 != null || s2 != null) {if (s1 != null && s2 != null) {
//都不為空 才有比較的必要int mergeResult = s1.compareTo(s2);if (mergeResult > 0) {//s1在s2后面writer.write(s2);writer.write(System.getProperty("line.separator"));s2 = br2.readLine();}if (mergeResult == 0) {//s1=s2writer.write(s1);								writer.write(System.getProperty("line.separator"));writer.write(s2);						writer.write(System.getProperty("line.separator"));
//						System.out.println("write time : " + writeTime++);s1 = br1.readLine();s2 = br2.readLine();}if (mergeResult < 0) {//s1在s2前面writer.write(s1);						writer.write(System.getProperty("line.separator"));s1 = br1.readLine();}}if (s1 == null && s2 != null) {writer.write(s2);writer.write(System.getProperty("line.separator"));s2 = br2.readLine();}if (s2 == null && s1 != null) {writer.write(s1);writer.write(System.getProperty("line.separator"));s1 = br1.readLine();}}br1.close();br2.close();
//			deleteFile(files[i]);
//			deleteFile(files[i + 1]);writer.close();}mergeSortCount++;multiWaysMergeSort(getTempFiles("last_" + (mergeSortCount-1) + "_"));
}