js中的插入排序

插入排序

插入排序的思想：将整个数组a分为有序和无序的两个部分。前者在左边，后者在右边。开始有序的部分只有a[0] , 其余都属于无序的部分
每次取出无序部分的第一个（最左边）元素，把它加入有序部分。假设插入合适的位置p，则原p位置及其后面的有序部分元素都向右移动一个位置，有序的部分即增加了一个元素。一直做下去，直到无序的部分没有元素

function insert(arr){
	//1. 准备一个新数组，用来存储抓到手里的牌，开始先抓一张牌进来
	let handle=[]
	handle.push(arr[0])
	//2. 从第二项开始一次抓牌，一直到把牌面上的牌抓光
	for(let i=1;i<arr.length;i++){
		//a是新抓的牌
		let a=arr[i]
		//和handle手里的牌一次比较（从后向前）
		for(let j=handle.length-1;j>=0;j--){
			//每一次要比较的手里的牌
			let b=handle[j]
			//如果当前新牌A比要比较的牌B大，把A放到B的后面
			if(a>b){
				handle.splice(j+1,0,a)
				break
			}
			//已经比到了第一项了，我们把新牌A放到最前面即可
			if(j===0){
				handle.unshift(a)
			}
		}
	}
	return handle
}
let arr=[1,5,3,7,8]
let result =insert(arr)
console.log(result)//[1, 3, 5, 7, 8]