對于較少的數進行排序,冒泡和歸并算法的優勢區分并不明顯,然而,這次對長度為1000000的數組進行排序。使用冒泡排序算法,簡直無情,曆時43分鐘有餘(2619秒)!而歸并排序算法對其實作僅僅使用了264毫秒,你沒看錯!相差的除了數值還有一個數量級!由此可見,算法的優化對于機器處理來說,其重要性不言而喻。
冒泡排序參考資料:http://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F
歸并排序參考資料:http://zh.wikipedia.org/wiki/%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F
程式實作:
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.text.DateFormat;
import java.util.Scanner;
public class Txt2Sort {
//傳回冒泡排序所用時間
public long bubbleSort(int[] dataArray){
DateFormat dfDefault = DateFormat.getInstance();
long startTime = System.currentTimeMillis();
System.out.println("\n冒泡排序開始時間:"+dfDefault.format(startTime));
//冒泡排序算法
for(int i=1,lineCount=dataArray.length;i<lineCount;i++)
for(int j=0;j<lineCount-i;j++){
if(dataArray[j]>dataArray[j+1]){
int t = dataArray[j];
dataArray[j] = dataArray[j+1];
dataArray[j+1] = t;
}
}
long endTime = System.currentTimeMillis();
System.out.println("冒泡排序結束時間:"+dfDefault.format(endTime));
long useTimeSeconds = (long)((endTime - startTime)/1000);
return useTimeSeconds;
}
//寫入檔案使用時長
public long writeToFile(int[] array,String fileName) throws FileNotFoundException{
DateFormat dfDefault = DateFormat.getInstance();//擷取時間,格式:3/27/14 10:50 PM
PrintWriter pw = new PrintWriter(new File(fileName));
long startTime = System.currentTimeMillis();
System.out.println("\n寫入檔案開始時間:"+dfDefault.format(startTime));
for(int i=0,lineCount=array.length;i<lineCount;i++){
pw.println(array[i]);
}
pw.close();
long endTime = System.currentTimeMillis();
System.out.println("寫入檔案結束時間:"+dfDefault.format(endTime));
long useTimeMills = (long)(endTime - startTime); //機關:毫秒
return useTimeMills;
}
//傳回歸并排序使用的時間
public long mergeSort(int[] needSortArray,int arrayLength,String fileName) throws FileNotFoundException{
int[] medium = new int[arrayLength];
DateFormat dfDefault = DateFormat.getInstance();
long startTime = System.currentTimeMillis();
System.out.println("歸并排序開始時間:"+dfDefault.format(startTime));
//排序
MergeAll(needSortArray, medium, arrayLength);
long endTime = System.currentTimeMillis();
System.out.println("歸并排序結束時間:"+dfDefault.format(endTime));
this.writeToFile(needSortArray, fileName);
long useTimeSeconds = (long)(endTime - startTime);
return useTimeSeconds;
}
//一次相鄰數組排序
public void MergeFirst(int[] r,int[] r1, int s,int m,int t){
//相鄰有序序列r[s]~r[m]和r[m+1]~r[t],合成有序序列r1[s]~r1[t]
//i,j分别指向相鄰有序序列的目前元素,k指向合成有序序列的目前元素
int i=s,j=m,k=s;
while(i<m && j<t){
if(r[i]<=r[j])
r1[k++] = r[i++];
else
r1[k++] = r[j++];
}
//處理未排序的序列,前半部分和後半部分
if(i<m)
while(i<m)
r1[k++]=r[i++];
else
while(j<t)
r1[k++]=r[j++];
}
//一層相鄰數組排序,從下标為0開始存放待排序列
public void MergeSecond(int[] r,int[] r1,int n,int h){
int i=0;
while(i<=n-2*h){
MergeFirst(r, r1, i,i+h,i+2*h);
i+=2*h;
}
//最後一個序列長度小于h(子序列的數組長度)
if(i<n-h)
MergeFirst(r, r1, i,i+h,n);
//排至剩下最後一個子序列
else
for(int k=i;k<n;k++)
r1[k]=r[k];
}
//全體二路歸并排序非遞歸實作
public void MergeAll(int[] r,int[] r1,int n){
int h=1;//h為初始子序列(h)長度
while(h<n){
MergeSecond(r, r1, n, h);//待排序列r傳至r1
h=2*h;
MergeSecond(r1, r, n, h);//待排序列r1傳回r
h=2*h;
}
}
//全體二路歸并排序遞歸實作
public static void main(String[] args) throws FileNotFoundException{
//從檔案讀取資料
int[] readCount = new int[1000000];
Scanner scan = new Scanner(new File(args[0]));//第一個個參數指定讀取的檔案名
while(scan.hasNextInt()){
for(int n=0,lineCount= readCount.length;n<lineCount;n++){
readCount[n] = scan.nextInt();
}
}
scan.close();
//冒泡排序調用,傳回排序時長
Txt2Sort t = new Txt2Sort();
long useSortTime = t.bubbleSort(readCount);
System.out.println("\n冒泡排序法使用時長:"+useSortTime+" seconds");
//寫入檔案調用,傳回寫入時長,第二個參數指定生成的檔案名
long useWriteTime = t.writeToFile(readCount,args[1]);
System.out.println("寫入檔案使用時長:"+useWriteTime+" mills");
long bubbleUseAllTime = useSortTime+useWriteTime;
System.out.println("冒泡排序總共使用時長:"+bubbleUseAllTime+" seconds");
//歸并排序調用,傳回排序時長
long MegerUseAllTime = t.mergeSort(readCount, readCount.length,args[1]);
System.out.println("歸并排序使用時長:"+MegerUseAllTime+" mills");
}
}
測試結果:
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0NXYFhGd192UvwVe0lmdhJ3ZvwFM38CXlZHbvN3cpR2Lc1TPB10QGtWUCpEMJ9CXsxWam9CXwADNvwVZ6l2c052bm9CXUJDT1wkNhVzLcRnbvZ2Lc1zYtJGcKhVWsh2VhZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39jMxMTOwMDN4ADOyMDM0EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)