快速排序处理文件

昨晚看到的一家公司出的程序题：输入文件的内容格式为一行一条数据，每条数据有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(); //方法体

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){