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程序设计有所帮助。