将数字插入已排序的数字数组的有效方法？

Question

我有一个已排序的JavaScript数组,并希望在数组中再插入一个项目,以便生成的数组保持排序状态.我当然可以实现一个简单的快速插入式插入功能:

var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
  array.splice(locationOf(element, array) + 1, 0, element);
  return array;
}

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (end-start <= 1 || array[pivot] === element) return pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

console.log(insert(element, array));

[警告] 此代码在尝试插入数组的开头时有一个错误,例如insert(2, [3, 7 ,9]产生错误的[3,2,7,9].

但是,我注意到Array.sort函数的实现可能会为我做这个,本机地:

var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
  array.push(element);
  array.sort(function(a, b) {
    return a - b;
  });
  return array;
}

console.log(insert(element, array));

是否有充分的理由选择第一个实施？

编辑:请注意,对于一般情况,O(log(n))插入(在第一个示例中实现)将比通用排序算法更快; 但是,特别是JavaScript并不一定如此.注意:

• 几种插入算法的最佳情况是O(n),它仍然与O(log(n))显着不同,但不如下面提到的O(n log(n))那么糟糕.它将归结为使用的特定排序算法(请参阅Javascript Array.sort实现？)
• JavaScript中的排序方法是一个本机函数,因此潜在地实现了巨大的好处 - 对于合理大小的数据集,具有巨大系数的O(log(n))仍然比O(n)差得多.

Answer 1

就像单个数据点一样,对于踢,我测试了这一点,使用在Windows 7上使用Chrome的两种方法将1000个随机元素插入到100,000个预先排序的数字的数组中:

First Method:
~54 milliseconds
Second Method:
~57 seconds

因此,至少在此设置中,本机方法无法弥补它.即使对于小数据集也是如此,将100个元素插入到1000的数组中:

First Method:
1 milliseconds
Second Method:
34 milliseconds

Answer 2

简单(演示):

function sortedIndex(array, value) {
    var low = 0,
        high = array.length;

    while (low < high) {
        var mid = (low + high) >>> 1;
        if (array[mid] < value) low = mid + 1;
        else high = mid;
    }
    return low;
}

Answer 3

一个非常有趣的讨论非常好,非常好的问题!在使用Array.sort()数千个对象推送数组中的单个元素后,我也在使用该函数.

我不得不locationOf为了我的目的扩展你的功能,因为它有复杂的对象,因此需要比较函数,如Array.sort():

function locationOf(element, array, comparer, start, end) {
    if (array.length === 0)
        return -1;

    start = start || 0;
    end = end || array.length;
    var pivot = (start + end) >> 1;  // should be faster than dividing by 2

    var c = comparer(element, array[pivot]);
    if (end - start <= 1) return c == -1 ? pivot - 1 : pivot;

    switch (c) {
        case -1: return locationOf(element, array, comparer, start, pivot);
        case 0: return pivot;
        case 1: return locationOf(element, array, comparer, pivot, end);
    };
};

// sample for objects like {lastName: 'Miller', ...}
var patientCompare = function (a, b) {
    if (a.lastName < b.lastName) return -1;
    if (a.lastName > b.lastName) return 1;
    return 0;
};

Answer 4

您的代码中存在错误.它应该是:

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (array[pivot] === element) return pivot;
  if (end - start <= 1)
    return array[pivot] > element ? pivot - 1 : pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

如果没有此修复,代码将永远无法在数组的开头插入元素.

Answer 5

您的插入函数假定给定数组已排序,它直接搜索可插入新元素的位置,通常只需查看数组中的一些元素.

数组的常规排序函数不能使用这些快捷方式.显然,它至少必须检查数组中的所有元素,看它们是否已经正确排序.仅这一事实使得一般排序比插入函数慢.

通用排序算法通常平均为O(n·log(n)),并且取决于实现,如果阵列已经排序,则实际上可能是最坏的情况,导致O(n ²)的复杂性.直接搜索插入位置只有O(log(n))的复杂性,所以它总是会快得多.

Answer 6

这是使用 lodash 的版本。

const _ = require('lodash');
sortedArr.splice(_.sortedIndex(sortedArr,valueToInsert) ,0,valueToInsert);

注意：sortedIndex 执行二分搜索。

Answer 7

我知道这是一个已经有答案的老问题,还有其他一些不错的答案.我看到一些答案提出你可以通过在O(log n)中查找正确的插入索引来解决这个问题 - 你可以,但是你不能在那个时候插入,因为数组需要被部分复制出去制作空间.

底线:如果您确实需要在排序数组中插入和删除O(log n),则需要不同的数据结构 - 而不是数组.你应该使用B树.对于大型数据集使用B树所获得的性能提升将使这里提供的任何改进相形见绌.

如果必须使用数组.我提供了以下代码,基于插入排序,当且仅当数组已经排序时才有效.这对于需要在每次插入后求助的情况很有用:

function addAndSort(arr, val) {
    arr.push(val);
    for (i = arr.length - 1; i > 0 && arr[i] < arr[i-1]; i--) {
        var tmp = arr[i];
        arr[i] = arr[i-1];
        arr[i-1] = tmp;
    }
    return arr;
}

它应该在O(n)中运行,我认为这是你能做的最好的.如果js支持多个赋值会更好. 这是一个可以玩的例子:

更新:

这可能会更快:

function addAndSort2(arr, val) {
    arr.push(val);
    i = arr.length - 1;
    item = arr[i];
    while (i > 0 && item < arr[i-1]) {
        arr[i] = arr[i-1];
        i -= 1;
    }
    arr[i] = item;
    return arr;
}

更新了JS Bin链接

Answer 8

以下是一些想法:首先,如果您真的关心代码的运行时,请务必了解调用内置函数时会发生什么!我不知道从javascript中下来,但是快速google的splice函数返回了这个,这似乎表明你每次调用都在创建一个全新的数组!我不知道它是否真的重要,但它肯定与效率有关.我看到Breton在评论中已经指出了这一点,但它肯定适用于您选择的任何数组操作函数.

无论如何,实际解决问题.

当我读到您想要排序时,我的第一个想法是使用插入排序!.它很方便,因为它在排序或接近排序的列表上以线性时间运行.因为你的数组只有1个元素乱序,所以它几乎排序(除了,大小为2或3的数组或其他什么,但在那时,来吧).现在,实现排序并不是太糟糕,但这可能是你不想处理的麻烦,而且,我不知道关于javascript的事情,以及它是否容易或困难或诸如此类.这消除了对查找功能的需求,你只需推送(正如布列塔尼建议的那样).

其次,你的"quicksort-esque"查找功能似乎是一个二进制搜索算法!这是一个非常好的算法,直观而快速,但有一个问题:很难正确实现.我不敢说你的是否正确(我希望它是,当然!:)),但如果你想使用它,要小心.

无论如何,总结:使用带插入排序的"push"将在线性时间内工作(假设数组的其余部分已排序),并避免任何杂乱的二进制搜索算法要求.我不知道这是不是最好的方法(数组的底层实现,也许是一个疯狂的内置函数做得更好,谁知道),但这对我来说似乎是合理的.:) - Agor.

Answer 9

对于少量的物品，差异很小。但是，如果要插入很多项或使用非常大的数组，则每次插入后调用.sort（）都会导致大量开销。

为此，我最终编写了一个非常漂亮的二进制搜索/插入函数，因此我想与大家分享。由于它使用while循环而不是递归，因此没有多余的函数调用，所以我认为性能将比任何最初发布的方法都要好。并且它默认情况下模拟默认的Array.sort()比较器，但是如果需要，可以接受自定义比较器功能。

function insertSorted(arr, item, comparator) {
    if (comparator == null) {
        // emulate the default Array.sort() comparator
        comparator = function(a, b) {
            if (typeof a !== 'string') a = String(a);
            if (typeof b !== 'string') b = String(b);
            return (a > b ? 1 : (a < b ? -1 : 0));
        };
    }

    // get the index we need to insert the item at
    var min = 0;
    var max = arr.length;
    var index = Math.floor((min + max) / 2);
    while (max > min) {
        if (comparator(item, arr[index]) < 0) {
            max = index;
        } else {
            min = index + 1;
        }
        index = Math.floor((min + max) / 2);
    }

    // insert the item
    arr.splice(index, 0, item);
};

如果您愿意使用其他库，lodash提供了sortedIndex和sortedLastIndex函数，可以使用它们代替while循环。潜在的两个缺点是：1）性能不如我的方法好（我不知道它的糟糕程度如何）和2）它不接受自定义比较器函数，仅接受用于比较值的方法（我假设使用默认的比较器）。