JS折半插入排序算法实例
本文实例讲述了JS折半插入排序算法。分享给大家供大家参考，具体如下：
functionpushArrayWithIndex(arr,index,value){//将元素添加到数组的指定位置
vartemArr=arr.slice(0,index);
temArr.push(value);
returntemArr.concat(arr.slice(index));
}
/*testforpushArrayWithIndex
vararr=[1,2,3,4,5];
arr=pushArrayWithIndex(arr,1,9);
console.log(arr);*/
functionsortInsert(arr){//插入排序
vartemArr=[];//临时数组，存储已排序项
functiongetSortTmpIndex(subArr,num){
varlen=subArr.length;
if(0==len)return0;//当数组为空时，返回最开始位置
varcpmIndex=Math.ceil(len/2);//计算中间元素所在位置
if(cpmIndex>len-1)cpmIndex=len-1;
if(num==subArr[cpmIndex]){//相等时直接返回
returncpmIndex;
}
if(num>subArr[cpmIndex]){//向后折半查找
cpmIndex++;
returncpmIndex+getSortTmpIndex(subArr.slice(cpmIndex),num);
}
if(num<subArr[cpmIndex]){//向前折半查找
returngetSortTmpIndex(subArr.slice(0,cpmIndex),num);
}
}
for(variinarr){
varindex=getSortTmpIndex(temArr,arr[i]);//查找arr[i]在temArr中的位置
console.log('index:',index,'num:',arr[i],'arr:',temArr);
temArr=pushArrayWithIndex(temArr,index,arr[i]);//将元素插入到查找位置
}
returntemArr;
}
vararr=[3,7,6,5,9,1,2,3,1,7,4];
console.log(arr);
arr=sortInsert(arr);
console.log(arr);
希望本文所述对大家JavaScript程序设计有所帮助。