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基本算法:冒泡排序,二分查找的简单实例全部内容了，希望大家多多支持毛票票~