js算法总结

数列求和

• 等差数列求和

function sum(a0,d,n){//a0->首项，d->公差，n->项数
	return (a0+(a0+(n-1)*d))*n/2;//（首项+末项）*项数/2
}

• 等比数列求和

function sum(a0,q,n){//a0->首项，q->公比，n->项数
	if(q!=1){
		return a0*(1-Math.pow(q,n))/(1-q);//首项*(1-公比的n次方)/(1-公比)
	}else{
		return a0*n;
	}
}

有序数组搜索

• 分治+递归

function indexOf(arr,val){
	var i=Math.floor(arr.length/2);
	if(arr[i]===val){
		return i;
	}
	if(arr.length==1){
		return -1;
	}
	if(val<arr[i]){
		return indexOf(arr.slice(0,i),val);
	}else{
		var result=indexOf(arr.slice(i+1),val);
		return result==-1?result:i+1+result;
	}
}

数组去重

Array.from(new Set(arr))//Set是ES6的新特性，是一种无序无重复元素的集合；Array.from也是ES6的新特性，将类数组转化为数组

数组排序

• 冒泡排序

function bubbleSort(arr){
	var l=arr.length;
	var tmp;
	var flag;
	for(var i=0;i<l;++i){
		flag=false;
		for(var j=0;j<l-i-1;++j){
			//相邻两个数比较，大的换到后面
			if(arr[j]>arr[j+1]){
				tmp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=tmp;
				flag=true;
			}
		}
		//如果这一轮循环没有出现交换，说明所有排序已经完成，直接结束所有循环
		if(!flag){
			break;
		}
	}
	return arr;
}

• 插入排序

function insertSort(arr){
	var l=arr.length;
	for(var i=1;i<l;++i){
		var item=arr[i];
		for(var j=0;j<i;++j){
			if(arr[j]>item){
				arr.splice(j,0,item);//将item插入到下标为j的位置
				arr.splice(i+1,1);//将原来的item删除
				break;
			}
		}
	}
	return arr;
}

• 快速排序

function quickSort(arr){
	var l=arr.length;
	if(l<=1){
		return arr;
	}
	var base=arr[0];//基准数
	var left=[],right=[];
	for(var i=1;i<l;i++){
		var item=arr[i];
		//小于基准数放左边，否则放右边
		if(item<base){
			left.push(item);
		}else{
			right.push(item);
		}
	}
	return quickSort(left).concat(base,quickSort(right));
}