算法—比較兩種排序算法：選擇排序和插入排序，排序算法

算法—比較兩種排序算法：選擇排序和插入排序，排序算法

現在我們已經實現了兩種排序算法，我們很自然地想知道選擇排序和插入排序哪種更快。這裡我們第一次用實踐說明我們解決這個問題的辦法。

性質：對於隨機排序的無重復主鍵的數組，插入排序和選擇排序的運行時間是平方級別的，兩者之比應該是一個較小的常數。

例證：這個結論在過去的半個世紀中已經在許多不同類型的計算機上經過了驗證。在1980年本書第一版完成之時插入排序就比選擇排序快一倍，現在仍然是這樣，盡管那時這些算法將10萬條數據排序需要幾個小時而現在只需要幾秒鐘。在你的計算機上插入排序也比選擇排序快一些嗎？可以通過SortCompare類來檢測。它會使用由命令行參數指定的排序算法名稱所對應的sort()方法進行指定次數的實驗（將指定大小的數組排序），並打印出所觀察到的各種算法的運行時間的比例。

我們使用Stopwatch來計時。

隨機數組的輸入模型由SortCompare類中的timeRandom-Input()方法實現。這個方法會生成隨機的Double值，將它們排序，並返回指定次測試的總時間。

用命令行參數指定重復次數的好處是能夠運行大量的測試（測試次數越多，每遍測試所需的平均時間就越接近於真實的平均數據）並且能夠減小系統本身的影響。

/**
 * 比較兩種排序算法
 * @author huazhou
 *
 */
public class SortCompare {
	public static double time(String alg, Comparable[] a){
		Selection selection = new Selection();
		Insertion insertion = new Insertion();

		Stopwatch timer = new Stopwatch();
		if(alg.equals("Selection")){
			selection.sort(a);
		}
		if(alg.equals("Insertion")){
			insertion.sort(a);
		}
		return timer.elapsedTime();
	}

	public static double timeRandomInput(String alg, int N, int T){
		//使用算法1將T個長度為N的數組排序
		double total = 0.0;
		Double[] a = new Double[N];
		for (int t = 0; t < T; t++) {
			//進行一次測試(生成一個數組並排序)
			for (int i = 0; i < N; i++) {
				a[i] = StdRandom.uniform();
			}
			total += time(alg, a);
		}
		return total;
	}

	public static void main(String[] args){
		String alg1 = args[0];
		String alg2 = args[1];
		int N = Integer.parseInt(args[2]);
		int T = Integer.parseInt(args[3]);
		double t1 = timeRandomInput(alg1, N, T);//算法1的總時間
		double t2 = timeRandomInput(alg2, N, T);//算法2的總時間
		StdOut.printf("For %d random Doubles\n	%s is", N, alg1);
		StdOut.printf(" %.1f times faster than %s\n", t2/t1, alg2);
	}
}

這個用例會運行由前兩個命令行參數指定的排序算法，對長度為N（由第三個參數指定）的Double型隨機數組進行排序，元素值均在0.0到1.0之間，重復T次（由第四個參數指定），然後輸出總運行時間的比例。

【源碼下載】