了解一个知识,必须先要从其含义开始。 折半插入排序,又称二分法插入排序。是由折半(二分法)排序和插入排序两种排序算法组合而成。折半(二分法)排序和插入排序不了解的同学可以先看看主页的两篇文章。 接下来,仍是用一个小例子解释折半插入排序是如何排序的。俄罗斯套娃大小排列
现如今,有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;
若是需要插入,就需要从最右侧开始,交换相邻元素位置,最后将元素插入到指定位置,具体实现方法为插入排序(插入排序算法具体由主页另一篇经典算法之插入排序文章)
学习折半二分法查找,到插入排序,在到折半插入排序,内容算法复杂度一点点的递增。犹如建房子需要打好地基,一点点的实施组合,才能建成高耸入云的楼房。知识需要一点点的积累,才能展现更大的才能。不积跬步无以至千里,不积小流无以成江海。