首页 / 脚本样式 / JavaScript / JS折半插入排序算法实例

function pushArrayWithIndex（arr, index, value） { // 将元素添加到数组的指定位置var temArr = arr.slice（0, index）;temArr.push（value）;return temArr.concat（arr.slice（index））;}/* test for pushArrayWithIndexvar 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）;