经典算法之折半插入排序
折半插入排序
排序含义
了解一个知识，必须先要从其含义开始。 折半插入排序，又称二分法插入排序。是由折半（二分法）排序和插入排序两种排序算法组合而成。折半（二分法）排序和插入排序不了解的同学可以先看看主页的两篇文章。 接下来，仍是用一个小例子解释折半插入排序是如何排序的。俄罗斯套娃大小排列
现如今，有5个大小不同的俄罗斯套娃A、B、C、D、E，按要求需要将这5个俄罗斯套娃按照从小到大的顺序排列。且套娃大小情况为【D>B>C>E>A】
首先先判断第一个和第二个套娃之间的关系，发现第二个套娃B是大于套娃A的，所以不需要排列。然后再看第二位和第三位B和C，发现B>C，不符合有小到大升序的规律，所以需要进行排序。首先，先找到C合适的位置，使用折半查找，另left左边界等于零，右边界right等于已知排好序的长度值减一，也就是循环的次数-1；然后获取其边界中间值后判断key值（需要插入的元素的值）与中间值的大小关系，并决定一个新的区间。若左边界不等于且大于右边界，则说明该值不存在，适合在此位置插入元素。然后执行插入元素。将需要插入的值与其左侧相邻的交换，直到该值到达需要插入的位置。此时套娃的大小关系是【A、C、B、D、E】。此时第三次循环i=3，将B与D比较，由大小情况可知，D>B的，所以不需要交换。此时大小位置是【A、C、B、D、E】。第四轮比较，比较D与E，由位置关系可知，并不符合升序规则，所以将E作为KEY标记值，在前面的有序数组当中进去折中取位置。具体操作与上一次排序相似。最后打印排序结果。
排序图例
第一次排列 A<B，不需要排列
第二次排列 B>C需要排列,且C>A，取AB中间值进行比较，则如图所示
第三次排列 由大小关系可知，符合升序结果，不排序
第四次排列 由大小关系可知，不符合升序规范，需要排序 首先，确定中间值比较大小
代码实现
定义数组
var arr=[11,45,23,51,20,42,33,85,62]封装排序方法
var mysearch=function(arr){
for(var i=1;i<arr.length;i++){
if(arr[i-1]>arr[i]){
var key=arr[i];
var left=0;
var right=i-1;
while(left<=right){
var mid =Math.floor((right-left)/2)+left;
if(arr[mid]<key){
left=mid+1
}else{
right=mid-1;
}
}
//插入位置
for(var j=i-1;j>=right+1;j--){
arr[j+1]=arr[j]
}
arr[right+1]=key;
}
}
}代码解析
外部for循环：遍历每一个数组
for(var i=1;i<arr.length;i++){
//方法体
}判断是否需要排序
if(arr[i-1]>arr[i]){
//方法体
}二分法查找位置
var key=arr[i];
var left=0;
var right=i-1;
while(left<=right){
var mid =Math.floor((right-left)/2)+left;
if(arr[mid]<key){
left=mid+1
}else{
right=mid-1;
}
}key值为需要排序的元素，令区域等于有序数列，也就是从数组开头到待排元素的前一位分别为元素的左右边界（二分法查找算法具体由主页另一篇折半选择文章）
插入元素
//插入位置
for(var j=i-1;j>=right+1;j--){
arr[j+1]=arr[j]
}
arr[right+1]=key;若是需要插入，就需要从最右侧开始，交换相邻元素位置，最后将元素插入到指定位置，具体实现方法为插入排序（插入排序算法具体由主页另一篇经典算法之插入排序文章）
总结
学习折半二分法查找，到插入排序，在到折半插入排序，内容算法复杂度一点点的递增。犹如建房子需要打好地基，一点点的实施组合，才能建成高耸入云的楼房。知识需要一点点的积累，才能展现更大的才能。不积跬步无以至千里，不积小流无以成江海。
腾讯云开发者
