JS折半插入排序算法实例

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

function pushArrayWithIndex(arr, index, value) { // 将元素添加到数组的指定位置

var temArr = arr.slice(0, index);

temArr.push(value);

return temArr.concat(arr.slice(index));

}

/* test for pushArrayWithIndex

var arr = [1, 2, 3, 4, 5];

arr = pushArrayWithIndex(arr, 1, 9);

console.log(arr);*/

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