插入数字到有序数组中的有效方法？
我有一个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); } }
