js基本算法:冒泡排序,二分查找的简单实例
知识扩充:
时间复杂度:算法的时间复杂度是一个函数,描述了算法的运行时间。时间复杂度越低,效率越高。
自我理解:一个算法,运行了几次时间复杂度就为多少,如运行了n次,则时间复杂度为O(n)。
1.冒泡排序
解析:1.比较相邻的两个元素,如果前一个比后一个大,则交换位置。
2.第一轮的时候最后一个元素应该是最大的一个。
3.按照步骤一的方法进行相邻两个元素的比较,这个时候由于最后一个元素已经是最大的了,所以最后一个元素不用比较。
functionsort(elements){ for(vari=0;i<elements.length-1;i++){ for(varj=0;j<elements.length-i-1;j++){ if(elements[j]>elements[j+1]){ varswap=elements[j]; elements[j]=elements[j+1]; elements[j+1]=swap; } } } } varelements=[3,1,5,7,2,4,9,6,10,8]; console.log('before:'+elements); sort(elements); console.log('after:'+elements);
2.快速排序
解析:快速排序是对冒泡排序的一种改进,第一趟排序时将数据分成两部分,一部分比另一部分的所有数据都要小。然后递归调用,在两边都实行快速排序。
functionquickSort(elements){ if(elements.length<=1){returnelements;} varpivotIndex=Math.floor(elements.length/2); varpivot=elements.splice(pivotIndex,1)[0]; varleft=[]; varright=[]; for(vari=0;i<elements.length;i++){ if(elements[i]<pivot){ left.push(elements[i]); }else{ right.push(elements[i]); } } returnquickSort(left).concat([pivot],quickSort(right)); }; varelements=[5,6,2,1,3,8,7,1.2,5.5,4.5]; alert(quickSort(elements));
3.插入排序
解析:
(1)从第一个元素开始,该元素可以认为已经被排序
(2)取出下一个元素,在已经排序的元素序列中从后向前扫描
(3)如果该元素(已排序)大于新元素,将该元素移到下一位置
(4)重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
(5)将新元素插入到下一位置中
(6)重复步骤2
insertSort:function(elements){ vari=1, j,step,key,len=elements.length; for(;i<len;i++){ step=j=i; key=elements[j]; while(--j>-1){ if(elements[j]>key){ elements[j+1]=elements[j]; }else{ break; } } elements[j+1]=key; } returnelements; }
2.二分查找
解析:二分查找,也为折半查找。首先要找到一个中间值,通过与中间值比较,大的放又,小的放在左边。再在两边中寻找中间值,持续以上操作,直到找到所在位置为止。
(1)递归方法
functionbinarySearch(data,item,start,end){ varend=end||data.length-1; varstart=start||0; varm=Math.floor((start+end)/2); if(item==data[m]){ returnm; }elseif(item<data[m]){ returnbinarySearch(data,item,start,m-1)//递归调用 }else{ returnbinarySearch(data,item,m+1,end); } returnfalse; } vararr=[34,12,5,123,2,745,32,4]; binary(arr,5);
(2)非递归方法
functionbinarySearch(data,item){ varh=data.length-1, l=0; while(l<=h){ varm=Math.floor((h+l)/2); if(data[m]==item){ returnm; } if(item>data[m]){ l=m+1; }else{ h=m-1; } } returnfalse; } vararr=[34,12,5,123,2,745,32,4]; binarySearch(arr,5);
以上就是小编为大家带来的js基本算法:冒泡排序,二分查找的简单实例全部内容了,希望大家多多支持毛票票~