图解从插入排序到二分插入排序的JS实现【附源代码】

介绍

        插入排序是基础排序中的一种经典算法，它利用了特别简单的思维将排序进行实现，他的优点是思路非常好理解，缺点是如果数据分散程度为反向数据占主要比例的话时间复杂度会变成最悲观的O(n^2),所以插入排序的时间复杂度是O(n)-O(n^2)根据数据分布情况排序的时间复杂度也不同。

思想

        插入排序的思想是从数组中的第二个元素开始跟它的上一个元素进行比较（以顺序排列为例子），比如它比前一个元素小，就与前一个元素交换，直到它变成第一个元素，或者它的上一个元素比他还小。

图解

        今天依然以每次的数组为例子进行讲解。

let arr = [13,2,7,21,8,65,2,0,1,9,14,7,63]

 结合图片我们可以看到我们只需要从第1号位置的元素开始依次和当前元素之前的元素对比，只要找到比自己大的元素就将他们向右移动，直到他前面的元素比自己小或者前面没有元素，这种方式就是依次找到自己的位置然后插入到对应位置，所以我们称之为插入排序。根据图片的插入流程我们分析，如果元素大部分有序的话我们做插入的步骤就会非常的少无限的接近O(n)，而当元素大部分逆序或者完全倒序的情况插入排序的时间复杂度就会退化到O(n^2)。

代码实现

我们通过图片描述的行为可以轻松的实现插入排序的逻辑如下

let arr = [13,2,7,21,8,65,2,0,1,9,14,7,63]
//执行排序
function sort(arr){
//从数组的第2个位置开始循环
	for(let i = 1;i<arr.length;i++){
//记录当前循环到的位置
		let temp = arr[i]
//从他的上一个元素开始比较
		let j = i-1
//找到比自己小的元素之前进行右移
		while(j>=0&&temp<arr[j]){
			arr[j+1] = arr[j]
			j--
		}
//将最后的位置设置为交换的元素
		arr[j+1] = temp
		console.log(arr)
	}
}
sort(arr)
console.log(arr)

优化方案

        从插入排序的情况我们总结来看这个排序还是有优化的空间的，当我们插入的数据越来越多左侧需要比较的数据长度无限接近于数组的长度，这样当我们后面的数据越小的话需要比较和移动的数据就越多，根据图片比较我们发现插入进行是元素前面的数据是直接有序的存在，所以这里我们可以结合2分查找的方式将插入的手段改造成2分插入的方式来做，这样我们的插入排序在做比较插入的逻辑就能从最悲观的比较次数简化到2分查找的虚拟树的深度，这里我们使用图片解释一下比较流程。

结合上图我们会发现使用二分插入之后我们的插入排序的比较次数就会变得很少。这样我们就能让插入排序的效率执行的更高，这种排序方式就是【二分插入法】。

进阶实现

let arr = [13,2,7,21,8,65,2,0,1,9,14,7,63]
function sort(arr){
	//执行对比
	for(let i = 1;i<arr.length;i++){
		let temp = arr[i]
		let j = i-1
		//执行二分插入
		insertHalf(0,j,temp,arr,i)
	}
}
/**
 * 二分插入算法
 * @param {Object} begin 起始位置
 * @param {Object} end 终止位置
 * @param {Object} val 当前插入的数值
 * @param {Object} arr 数组对象
 * @param {Object} lastIndex 当前插入的数值的下标
 */
function insertHalf(begin,end,val,arr,lastIndex){
	//如果起始位置比终止位置小
	if(begin<end){
		//求中值
		let mid = Math.floor((end+begin)/2)
		//如果插入的比中值大
		if(val>=arr[mid]){
			//继续二分
			insertHalf(mid+1,end,val,arr,lastIndex)
		}else{
			//如果插入的比中值小，继续二分
			insertHalf(begin,mid,val,arr,lastIndex)
		}
	}else{
		//二分结束，比较内容进行插入
		let i = lastIndex-1
		if(val>= arr[i]){
			arr[i+1] = val
			return
		}
		while(i>=begin){
			arr[i+1] = arr[i]
			i--
		}
		console.log(i)
		arr[i+1] = val
	}
}

sort(arr)
console.log(arr)

 总结

        插入排序除了使用二分法可以进一步优化之后还可以进阶为【希尔排序】，后续我们再针对希尔排序做进一步的说明。