JavaScript实现对三种基本排序算法的计时比较

拼搏现实的明天。 2022-03-02 15:52 105阅读 0赞

冒泡、选择、插入是三种基本的排序算法，那么谈们的执行效率如何呢？接下来我们将随机生成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）冒泡排序：

(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)插入排序

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+"毫秒");

在控制台的输出结果为：

![在这里插入图片描述][20190320204519238.png]  
很明显，插入排序耗用时间最少，冒泡排序耗费时间做多，而选择排序处于二者之间，但也明显优于冒泡排序。如果继续加大数集的样本，差距会更加明显。

这充分证明了三种排序的执行效率：

插入排序 > 选择排序 > 冒泡排序

[20190320204519238.png]: /images/20220302/fe890c8731f64903bbcdba981c76ed71.png