昨晚看到的一家公司出的程序題：輸入文件的內容格式為一行一條數據，每條數據有2個字段用逗號分隔，第1個字段為排序用的Key，第二個字段為value。換行符為’/n’。
數據內容舉例如下:
abe,xmflsflmfmlsmfs
abc,xmlmxlkmffhf
8fj3l,xxjfluu313ooo11
注意點:
本次的測試數據內容都是ASCII字符，無中文漢字。所以不必考慮字符集。
本次的測試數據中key的最大長度8，value的最大長度32。
請勿使用諸如java.util.Collections.sort(), java.util.Arrays.sort()這樣的JDK提供的排序函數。
請勿使用多線程。
排序以key的升序，key的比較大小以String.compareTo()為準。最后排序完成的數據寫入指定的輸出文件。另外還提供一個指定的臨時文件，在處理大量數據的時候會用到。 以下是我的代碼： 主函數： public static void main(String[] args) throws Exception { long start = System.currentTimeMillis(); //方法體
File inputFile = new File("data/input.data"); File outputFile = new File("data/output.data"); File tempFile = new File("data/temp.data"); if(!inputFile.exists()){ System.out.test方法： public static void test(File inputFile, File outputFile, File tempFile) throws Exception { //用BufferedReader來對文件進行讀取，整行讀取覺得速度比較快 FileReader fReader = new FileReader(inputFile); BufferedReader bufReader = new BufferedReader(fReader); String read; ArrayList list = new ArrayList();//保存讀取的文件 while((read=bufReader.readLine())!=null){ list.add(read); } list.trimToSize();//除去ArrayList中預留元素的位置，節約內存 bufReader.close(); fReader.close(); quicksort(list, 0, list.size()-1);//調用快速排序的方法 //用FileOutputStream 進行寫文件到outputFile FileOutputStream out=new FileOutputStream(outputFile); //逐行寫文件 for (int i=0;i<=list.size()-1;i++) { StringBuffer sb = new StringBuffer(); // System.out.println(list.get(i)+”/r/n”); sb.append(list.get(i)+”/r/n”); out.write(sb.toString().getBytes(“utf-8”)); } out.close(); } 快速排序方法： //主要用的是遞歸法來進行排序，當list的起始位置low和結束位置high相等時，遞歸結束 public static void quicksort(ArrayList list, int low, int high){ if(low < high){ int middle = getMiddle(list, low, high);//調用getMiddle方法，得到中軸位置 quicksort(list, low, middle-1); quicksort(list, middle+1, high); } } getMiddle方法： /** * * @param list * @param low list初始位置 * @param high list末尾位置 * @return 返回最終的low值，即中軸所在位置 */ public static int getMiddle(ArrayList list, int low, int high){ String tempKey = list.get(low).toString();//將list起始位的數據作為軸 while(low < high){ //從后往前比較，如果list.get(high).toString()比tempKey 值大，位置不變，就比較下一位置的值 while(low < high && swap(list.get(high).toString(), tempKey)){ high –; } //如果list.get(high).toString()比tempKey 值小，把list.get(high).toString()的值賦值給list.get(low)，然后從前往后比較值 list.set(low, list.get(high)); while(low < high && !swap(list.get(low).toString(), tempKey)){ low ++; } list.set(high, list.get(low)); } //當所有值都比較完之后，把tempkey的值賦值給list.get(low),此時low的位置即為中軸的位置 list.set(low, tempKey); return low; } swap方法： /** * * @param str1 * @param str2 * @return 如果 str1的key值小于str2的key值，返回true，否則返回false */ public static boolean swap(String str1,String str2){ String Key1,Key2; Key1 = str1.split(",")[0];//將str1第一個逗號前的字符串賦值給key1 Key2 = str2.split(",")[0];//將str2第一個逗號前的字符串賦值給key2 if(Key2.compareTo(Key1)<0){ return true; } else{ return false; } }快速排序思想：假設將5 7 6 3 1 9 2 8進行升序排序，首先選一個中軸（一般選開頭數值）來和其他數進行比較，把比中軸小的值放在它左邊，比它大的放右邊，第一次排序：**2 1 3** 5 **6 9 7 8** //5前面都比5小，5后面都比5大第二次排序：（**1** 2 **3**） 5（ 6 **9 7 8**）//2和6為軸第三次排序：1 2 3 5 6（ **8 7** 9 ）//9為軸第四次排序：1 2 3 5 6 （**7** 8 )9 //7為軸新聞熱點
疑難解答
