javascript - 如何在排序数组中插入值并保持数组排序？

Question

在数组中插入值并保持数组排序的最佳方法是什么？

例如，这是一个数组

const arr = [1, 4, 23, 45];

我可以使用方法 push 或 splice 添加一个新值，例如 16，我将得到修改后的数组:

[1, 4, 23, 45, 16]

但我需要保持数组排序:

[1, 4, 16, 23, 45]

保持数组有序的更好方法是什么？我应该每次添加新值时都排序，还是检测插入新值所需的索引？

Answer 1

看看复杂性:

• 排序:最佳情况下的时间复杂度为 O(nlogn)
• 索引插入:最坏情况下的 O(n)
• 智能排序:在最佳情况下，使用插入排序等算法的时间复杂度为 O(n)，当数组几乎已经排序时，该算法效果非常好
• 二进制插入:O(logn) 这是首选方式

function  binaryInsertion(arr, element) {
    return binaryHelper(arr, element, 0, arr.length - 1);
}

function binaryHelper(arr, element, lBound, uBound) {
    if (uBound - lBound === 1) {
        // binary search ends, we need to insert the element around here       
        if (element < arr[lBound]) arr.splice(lBound, 0, element);
        else if (element > arr[uBound]) arr.splice(uBound+1, 0, element);
        else arr.splice(uBound, 0, element);
    } else {       
        // we look for the middle point
        const midPoint = Math.floor((uBound - lBound) / 2) + lBound;
        // depending on the value in the middle, we repeat the operation only on one slice of the array, halving it each time
        element < arr[midPoint]
            ? binaryHelper(arr, element, lBound, midPoint)
            : binaryHelper(arr, element, midPoint, uBound);
    }
}

console.log("even array test");
var array = [1,3,4,5,9];
binaryInsertion(array, 2);
console.log(array);

console.log("odd array test");
var array = [1,3,5,7,9,11,13,15];
binaryInsertion(array, 10);
console.log(array);

console.log("beginning and end test");
var array = [2,3,4,5,9];
binaryInsertion(array, 0);
binaryInsertion(array, 10);
console.log(array);