JavaScript實作對三種基本排序算法的計時比較

冒泡、選擇、插入是三種基本的排序算法，那麼談們的執行效率如何呢？接下來我們将随機生成10000個0~10000之間的數字，用這三種算法分别進行排序，比較它們消耗的時間，以此來觀察執行效率的不同。

1.建立數集

首先，建立三個數組，并将其各自加入10000個随機生成的數值：

var arr1 = [];
		var arr2 = [];
		var arr3 = [];
		for(var i = 0;i < 10000;i++){
			num = Math.ceil(Math.random()*10000);
			arr1.push(num);
			arr2.push(num);
			arr3.push(num);
		}
           

2.封裝函數

将冒泡、選擇、插入三種排序算法分别封裝為三個函數，以便于執行。

（1）冒泡排序：

function bubble(){
			for(var i=0;i<arr1.length-1;i++){
				for(var j=0;j<arr1.length-i-1;j++){
					if(arr1[j]>arr1[j+1]){
						tem = arr1[j];
						arr1[j] = arr1[j+1];
						arr1[j+1] = tem;
					}
				}
			}
		}
           

(2）選擇排序

var min,temp;
		
		function selection(){
			for(var outer = 0;outer <= arr2.length-2;outer++){
				min = outer;
				for(var inner = outer + 1;inner <=arr2.length-1;inner++){
					if(arr2[inner]<arr2[min]){
						min = inner;
						temp = arr2[min];
						arr2[min] = arr2[outer];
						arr2[outer] = temp;
					}	
				}
			}
		}
           

(3)插入排序

function insertion(){
			var tem2,inner2;

			for(var outer2 = 1;outer2 <= arr3.length-1;outer2++){
				tem2 = arr3[outer2];
				inner2 = outer2;
				while(inner2 > 0 && arr3[inner2-1]>arr3[inner2]){
					arr3[inner2] = arr3[inner2-1];
					inner2--;
					arr3[inner2] = tem2;
				}
			}
		}
           

3.使用Data對象的

getTime()

方法進行計時

在開始和結束分别進行計時，将其時間相減，得出耗費的時間。

var start1 = new Date().getTime();
		bubble(arr1);
		var stop1 = new Date().getTime();
		var time1 = stop1 - start1;
		console.log("冒泡排序用時"+time1+"毫秒");

		var start2 = new Date().getTime();
		selection(arr2);
		var stop2 = new Date().getTime();
		var time2 = stop2 - start2;
		console.log("選擇排序用時"+time2+"毫秒");

		var start3 = new Date().getTime();
		insertion(arr3);
		var stop3 = new Date().getTime();
		var time3 = stop3 - start3;
		console.log("插入排序用時"+time3+"毫秒");
           

在控制台的輸出結果為：

很明顯，插入排序耗用時間最少，冒泡排序耗費時間做多，而選擇排序處于二者之間，但也明顯優于冒泡排序。如果繼續加大數集的樣本，差距會更加明顯。

這充分證明了三種排序的執行效率：

插入排序 > 選擇排序 > 冒泡排序