JS折半插入排序算法实例

时间:2021-05-26

本文实例讲述了JS折半插入排序算法。分享给大家供大家参考,具体如下:

function pushArrayWithIndex(arr, index, value) { // 将元素添加到数组的指定位置 var temArr = arr.slice(0, index); temArr.push(value); return temArr.concat(arr.slice(index));}function sortInsert(arr) { // 插入排序 var temArr = []; // 临时数组,存储已排序项 function getSortTmpIndex(subArr, num) { var len = subArr.length; if(0 == len) return 0; // 当数组为空时,返回最开始位置 var cpmIndex = Math.ceil(len / 2); // 计算中间元素所在位置 if(cpmIndex > len - 1) cpmIndex = len - 1; if(num == subArr[cpmIndex]) { // 相等时直接返回 return cpmIndex; } if(num > subArr[cpmIndex]) { // 向后折半查找 cpmIndex++; return cpmIndex + getSortTmpIndex(subArr.slice(cpmIndex), num); } if(num < subArr[cpmIndex]) { // 向前折半查找 return getSortTmpIndex(subArr.slice(0, cpmIndex), num); } } for (var i in arr) { var index = getSortTmpIndex(temArr, arr[i]); // 查找arr[i]在temArr中的位置 console.log('index:', index, ' num:', arr[i], ' arr:', temArr); temArr = pushArrayWithIndex(temArr, index, arr[i]); // 将元素插入到查找位置 } return temArr;}var arr = [3, 7, 6, 5, 9, 1, 2, 3, 1, 7, 4];console.log(arr);arr = sortInsert(arr);console.log(arr);

希望本文所述对大家JavaScript程序设计有所帮助。

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章