插入数字到有序数组中的有效方法?

我有一个sorting的JavaScript数组,并且想要插入一个更多的项目到数组中,因此结果数组保持sorting。 我当然可以实现一个简单的quicksort风格的插入函数:

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)); 

不过,我注意到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)); 

第二个select第一个实施是否有很好的理由?

编辑 :请注意,对于一般情况下,O(log(n))插入(在第一个示例中实现)将比通用sortingalgorithm更快; 然而对于JavaScript尤其如此。 注意:

  • 对于几种插入algorithm,最好的情况是O(n),它与O(log(n))仍然有很大的不同,但是不如O(n log(n))那样差。 这将涉及到使用的特定sortingalgorithm(请参阅JavaScript Array.sort实现? )
  • JavaScript中的sorting方法是一个本地函数,因此可能实现巨大的优势 – 对于合理大小的数据集,具有巨大系数的O(log(n))仍然可能比O(n)差得多。

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

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

所以,至less在这个设置上,本地方法不能弥补它。 即使对于小数据集也是如此,将100个元素插入1000:

 First Method: 1 milliseconds Second Method: 34 milliseconds 

非常好的和非凡的问题,一个非常有趣的讨论! 在使用数千个对象推送数组中的单个元素之后,我也正在使用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; }; 

简单( 演示 ):

 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; } 

你的代码有一个错误。 它应该是:

 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); } } 

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

你的插入函数假设给定的数组是sorting的,它直接search新元素可以插入的位置,通常只需要查看数组中的一些元素即可。

数组的一般sortingfunction不能使用这些快捷方式。 显然它至less要检查数组中的所有元素,看它们是否已经被正确的sorting。 仅仅这个事实使得一般sorting比插入函数慢。

一般的sortingalgorithm通常平均为O(n·log(n)) ,根据实现情况,如果数组已经sorting,实际上可能是最坏的情况,导致O(n 2 )的复杂性。 直接search插入位置只是O(log(n))的复杂度,所以它总是快得多。

这里有一些想法:首先,如果你真的关心你的代码的运行时间,一定要知道当你调用内置函数时会发生什么! 我不知道从下来的JavaScript,但快速谷歌的拼接函数返回这似乎表明你正在创build一个全新的数组每个调用! 我不知道这是否真的很重要,但这当然与效率有关。 我看到布列塔尼在评论中已经指出了这一点,但它肯定适用于你select的任何数组操纵function。

无论如何,到实际解决问题。

当我读到你想sorting,我的第一个想法是使用插入sorting! 。 这是很方便的,因为它在线性时间上运行在已sorting或接近sorting的列表上 。 因为你的数组只有1个元素不按顺序排列,所以这个algorithm被sorting为几乎(除了2或3的数组或者任何其他的数组,除了这个之外)。 现在,实现这个并不算太坏,但是这是一个你可能不想处理的麻烦,而且,我不知道关于JavaScript的一些东西,如果它很容易,或者很难或者不是。 这消除了你的查找function的需要,你只是推(如布列塔尼build议)。

其次,你的“quicksort-esque”查找function似乎是一个二进制searchalgorithm! 这是一个非常好的algorithm,直观快速,但有一个问题:正确实施是非常困难的。 我不敢说你的是否正确(我希望当然是!:)),但是要保持警惕。

不pipe怎样,摘要:在插入sorting中使用“push”将在线性时间内工作(假设数组的其余部分被sorting),并避免任何混乱的二进制searchalgorithm要求。 我不知道这是否是最好的方法(数组的底层实现,也许是一个疯狂的内置函数更好,谁知道),但对我来说似乎是合理的。 🙂 – Agor。

对于less数项目,差异是相当微不足道的。 但是,如果插入大量项目,或者使用非常大的数组,则在每次插入后调用.sort()将导致巨大的开销。

为了这个确切的目的,我写了一个漂亮的二进制search/插入函数,所以我想我会分享它。 因为它使用了一个while循环而不是recursion,所以没有额外的函数调用,所以我认为性能将比原来的方法更好。 它默认模拟默认的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)它不接受自定义的比较函数,只有一个获取值的方法(使用默认的比较器,我假设)。

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

底线:如果你真的需要O(log n)插入和删除一个有序数组,你需要一个不同的数据结构 – 而不是一个数组。 你应该使用一棵B树 。 使用B-Tree处理大型数据集会带来的性能提升,将使这里所提供的任何改进都相形见绌。

如果你必须使用一个数组。 我提供了下面的代码,基于插入sorting,它的工作, 当且仅当数组已经sorting。 这对于每次插入之后需要求助的情况都很有用:

 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链接

每个项目之后不要重新sorting

如果只有一个项目要插入,则可以使用二分查找find要插入的位置。 然后使用memcpy或类似的方式批量复制剩余的项目,为插入的项目留出空间。 二进制search是O(log n),副本是O(n),总共给出O(n + log n)。 使用上面的方法,每次插入之后都要重新sorting,即O(n log n)。

有关系吗? 假设你随机插入k个元素,其中k = 1000。sorting后的列表是5000个项目。

  • Binary search + Move = k*(n + log n) = 1000*(5000 + 12) = 5,000,012 = ~5 million ops
  • Re-sort on each = k*(n log n) = ~60 million ops

如果要插入的k个项目到达,则必须执行search+移动。 但是,如果您提供了一个k项目列表,以提前插入到已sorting的数组中 – 那么您可以做得更好。 对已sorting的n个数组分别sortingk个项目。 然后做一个扫描sorting,在这个sorting中,你同时向下移动两个sorting的数组,将一个sorting到另一个。 – 一步合并sort = k log k + n = 9965 + 5000 =〜15,000 ops

更新:关于你的问题。
First method = binary search+move = O(n + log n)Second method = re-sort = O(n log n)解释你得到的时机。

 function insertOrdered(array, elem) { let _array = array; let i = 0; while ( i < array.length && array[i] < elem ) {i ++}; _array.splice(i, 0, elem); return _array; } 
 Array.prototype.sortPush = function (itm, min, max){ min = min || 0; max = max || this.length; if (max == min) { this[0] = itm; } else if (itm <= this[min]) { this.splice(min, 0, itm); } else if (itm >= this[max]) { this.splice(max+1, 0, itm); } else { this.sortPush(itm, min+1, max-1); } }