эффективный способ вставить число в отсортированный массив чисел?

<p>просто как единая точка данных, для пинка я тестировал это, вставляя 1000 случайных элементов в массив из 100 000 предварительно отсортированных чисел, используя два метода с использованием chrome в windows 7:</p><pre><code>first method: ~54 milliseconds second method: ~57 seconds </code></pre><p>так что, по крайней мере, на этой установке нативный метод не восполняет это. это верно даже для небольших наборов данных, вставляя 100 элементов в массив из 1000:</p><pre><code>first method: 1 milliseconds second method: 34 milliseconds </code></pre>

<p>очень хороший и замечательный вопрос с очень интересной дискуссией! я также использовал функцию <code>array.sort()</code> после добавления одного элемента в массив с несколькими тысячами объектов.</p><p>мне пришлось расширить вашу функцию <code>locationof</code> для моих целей из-за наличия сложных объектов и, следовательно, необходимости в функции сравнения, как в <code>array.sort()</code>:</p><pre><code>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; }; </code></pre>

<p>в вашем коде есть ошибка. следует читать:</p><pre><code>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); } } </code></pre><p>без этого исправления код никогда не сможет вставить элемент в начало массива.</p>

<p>ваша функция вставки предполагает, что данный массив отсортирован, она ищет непосредственно место, где можно вставить новый элемент, обычно просто просматривая несколько элементов в массиве.</p><p>общая функция сортировки массива не может использовать эти ярлыки. очевидно, что, по крайней мере, необходимо проверить все элементы в массиве, чтобы убедиться, что они уже правильно упорядочены. уже один этот факт делает общую сортировку медленнее, чем функция вставки.</p><p>общий алгоритм сортировки обычно находится в среднем<em> o (n ⋅ log (n)) </em>и в зависимости от реализации это может быть на самом деле худший случай, если массив уже отсортирован, что приводит к сложностям<em> o (n<sup>2</sup>) </em>. прямой поиск позиции вставки имеет сложность<em> o(log(n)) </em>, поэтому он всегда будет намного быстрее.</p>

<p>для небольшого количества предметов разница довольно незначительная. однако, если вы вставляете много элементов или работаете с очень большим массивом, вызов .sort () после каждой вставки вызовет огромные накладные расходы.</p><p>в итоге я написал довольно удобную двоичную функцию поиска/вставки для этой цели, поэтому решил поделиться ею. поскольку вместо рекурсии используется цикл <code>while</code>, дополнительных вызовов функций не слышно, поэтому я думаю, что производительность будет даже лучше, чем у любого из первоначально опубликованных методов. и он по умолчанию эмулирует компаратор <code>array.sort()</code> по умолчанию, но при желании принимает пользовательскую функцию компаратора.</p><pre><code>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); }; </code></pre><p>если вы открыты для использования других библиотек, lodash предоставляет функции <a href="https://lodash.com/docs#sortedindex">sortedindex</a> и <a href="https://lodash.com/docs#sortedlastindex">sortedlastindex</a> , которые можно использовать вместо цикла <code>while</code>. два возможных недостатка: 1) производительность не так хороша, как у моего метода (хотя я не уверен, насколько она хуже) и 2) она не принимает пользовательскую функцию сравнения, только метод получения значения для сравнения (используя компаратор по умолчанию, я полагаю).</p>

<p>вот сравнение четырех различных алгоритмов для достижения этой цели: <a href="https://jsperf.com/sorted-array-insert-comparison/1">https://jsperf.com/sorted-array-insert-comparison/1</a> </p><p>алгоритмы</p><ul> <li>наивный: просто нажмите и сортировать () потом</li> <li>линейный: итерация по массиву и вставка в случае необходимости</li> <li>двоичный поиск: взят из <a href="https://stackoverflow.com/a/20352387/154329">https://stackoverflow.com/a/20352387/154329</a> </li> <li>«быстрая сортировка лайка»: изысканный раствор от syntzerzero ( <a href="https://stackoverflow.com/a/18341744/154329">https://stackoverflow.com/a/18341744/154329</a> )</li> </ul><p>наивный всегда ужасен. кажется, для небольших размеров массивов остальные три не отличаются слишком сильно, но для больших массивов последние 2 превосходят простой линейный подход.</p>

<pre><code>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; } </code></pre>

<p>вот версия, которая использует lodash.</p><pre><code>const \_ = require('lodash'); sortedarr.splice(\_.sortedindex(sortedarr,valuetoinsert) ,0,valuetoinsert); </code></pre><p>примечание: sortedindex выполняет бинарный поиск.</p>

<p>не пересортируйте после каждого предмета, его перебор.</p><p>если есть только один элемент для вставки, вы можете найти место для вставки с помощью бинарного поиска. затем используйте memcpy или аналогичное для массового копирования оставшихся элементов, чтобы освободить место для вставленного. двоичный поиск - o (log n), а копия - o (n), что дает o (n + log n) всего. используя методы выше, вы делаете повторную сортировку после каждой вставки, которая является o (n log n).</p><p>это имеет значение? допустим, вы случайным образом вставляете k элементов, где k = 1000. отсортированный список состоит из 5000 элементов. </p><ul> <li><code>binary search + move = k*(n + log n) = 1000*(5000 + 12) = 5,000,012 = ~5 million ops</code></li> <li><code>re-sort on each = k*(n log n) = ~60 million ops</code></li> </ul><p>если k элементов для вставки поступают когда-либо, то вы должны выполнить поиск + перемещение. однако, если вам дается список из k элементов для вставки в отсортированный массив - заблаговременно - тогда вы можете сделать еще лучше. сортировать k элементов отдельно от уже отсортированного массива n. затем выполните сортировку, в которой вы перемещаете оба отсортированных массива одновременно, сливая один в другой. - одношаговая сортировка слиянием = k log k + n = 9965 + 5000 = ~ 15 000 операций</p><p>обновление: по вашему вопросу.<br> <code>first method = binary search+move = o(n + log n)</code>. <code>second method = re-sort = o(n log n)</code> точно объясняет время, которое вы получаете.</p>