1 function swap(arr,index1,index2){ 2 var t = arr[index1]; 3 arr[index1] = arr[index2]; 4 arr[index2] = t; 5 } 6 function Sarray(num){ 7 this.nums = []; 8 this.num = num; 9 } 10 Sarray.prototype.init = function() { 11 for (i=0;i<this.num;i++){ 12 this.nums.push(Math.floor(Math.random()*(this.num+1))); 13 } 14 }; 15 Sarray.prototype.bubbleSort = function(){ 16 for (var i=this.nums.length;i>1;i--){ 17 for (var j=0;j<i;j++){ 18 if(this.nums[j]>this.nums[j+1]){ 19 swap(this.nums,j,j+1); 20 } 21 } 22 } 23 } 24 Sarray.prototype.selectionSort = function(){ 25 for (var i=0;i<this.nums.length-1;i++){ 26 var min = i; 27 for (var j=i+1;j<this.nums.length;j++){ 28 if(this.nums[min]>this.nums[j]){ 29 min = j; 30 } 31 } 32 if(min!=i){ 33 swap(this.nums,i,min); 34 } 35 } 36 } 37 Sarray.prototype.insertSort = function(){//默认0号位置有序 38 for (var i=1;i<this.nums.length;i++){ 39 var tem = this.nums[i]; 40 var j = i; 41 while(this.nums[j-1]>tem&&j>0){ 42 this.nums[j] = this.nums[j-1]; 43 j--; 44 } 45 this.nums[j] = tem; 46 } 47 } 48 var n=10000; 49 var a = new Sarray(n); 50 var b = new Sarray(n); 51 var c = new Sarray(n); 52 a.init(); 53 b.init(); 54 c.init(); 55 var start = new Date().getTime(); 56 a.bubbleSort(); 57 var end = new Date().getTime(); 58 console.log("冒泡排序用时:"+(end-start)+"ms"); 59 start = new Date().getTime(); 60 b.selectionSort(); 61 end = new Date().getTime(); 62 console.log("选择排序用时:"+(end-start)+"ms"); 63 start = new Date().getTime(); 64 c.insertSort(); 65 end = new Date().getTime(); 66 console.log("插入排序用时:"+(end-start)+"ms");
参考书籍:《数据结构与算法javascript描述》,我看的是pdf版。书上代码有错,已经进行修改。以上代码介绍了冒泡排序,选择排序,和插入排序,并通过对随机数的排序实验展现出他们的排序效率,可以直接拖到自己的控制台中测试。
说明:Sarray实例化时出入的参数代表的是要生成随机数的数量,init方法是生成随机数。bubbleSort是冒泡排序,selectionSort是选择排序,insertSort是插入排序,下次会再学习高级排序算法