Это быстрее для сортировки списка после вставки объектов или добавления их к отсортированному списку

Обычно намного лучше использовать "куча" . короче говоря, это разделяет стоимость поддержания порядка между толкателем и средством выбора. Обе операции являются O (зарегистрируйте n), вместо O (n регистрируют n), как большинство других решений.

В принципе это быстрее для создания дерева, чем отсортировать список. Дерево вставляет, O (журнал (n)) для каждого вставляют, ведя к полному O (журнал n (n)). Сортировка в O (журнал n (n)).

Вот почему Java имеет TreeMap, (в дополнение к TreeSet, TreeList, ArrayList и реализациям LinkedList Списка.)

• А TreeSet сохраняет вещи в объектном порядке сравнения. Ключ определяется интерфейсом Comparable.

• А LinkedList сохраняет вещи в порядке вставки.

• ArrayList использует больше памяти, быстрее для некоторых операций.

• А TreeMap, точно так же устраняет необходимость отсортировать по ключу. Карта создается в ключевом порядке во время вставок и сохраняется в отсортированном порядке в любом случае.

Однако по некоторым причинам, реализация Java TreeSet вполне немного медленнее, чем использование ArrayList и вида.

[Трудно размышлять относительно того, почему это было бы существенно медленнее, но это. Это должно быть немного быстрее одной передачей через данные. Такого рода вещь часто является стоимостью управления памятью, превосходящего алгоритмический анализ.]

Это о том же. Вставка объекта в отсортированный список является O (зарегистрируйте N), и выполнение этого для каждого элемента в списке, N, (таким образом создание списка) было бы O (N, регистрируют N), который является скоростью quicksort (или сортировка слиянием, которая ближе к этому подходу).

, Если бы Вы вместо этого вставили их на переднюю сторону, это был бы O (1), но выполнение quicksort после, это все еще будет O (N, регистрируют N).

я пошел бы с первым подходом, потому что он имеет потенциал, чтобы быть немного быстрее. Если начальный размер Вашего списка, N, намного больше, чем число элементов вставить, X, то подход вставки является O (X журналов N). Сортировка после вставки в заголовок списка является O (N, регистрируют N). Если N=0 (IE: Ваш список первоначально пуст), скорость вставки в отсортированный порядок, или сортировка впоследствии является тем же.

Если список a) уже отсортирован и b) динамичным по своей природе, затем вставление в отсортированный список должно всегда быть быстрее (найдите правильное место (O (n)) и вставьте (O (1))).

Однако, если список статичен, то перестановка остатка от списка должна произойти (O (n), чтобы найти, что правильное место и O (n) двигают вещи вниз).

Так или иначе, вставляя в отсортированный список (или что-то как Дерево двоичного поиска) должно быть быстрее.

O (n) + O (n) должен всегда быть быстрее, чем O (N, регистрируют n).

Я сказал бы, давайте протестируем его!:)

я попробовал quicksort, но сортировка почти сортирующего массива с quicksort... хорошо, не действительно хорошая идея. Я попробовал измененный, убегающий в 7 элементах и использующий вид вставки для этого. Однако, ужасная производительность. Я переключился на сортировку слиянием. Возможно, требовалась бы довольно большую память для сортировки (это не существует), но производительность намного лучше на сортированных массивах и почти идентична на случайных (начальный вид занял почти то же время для обоих, quicksort был незначительно быстрее).

Это уже показывает одну вещь: ответ на Ваши вопросы зависит сильно от алгоритма сортировки, который Вы используете. Если это будет иметь низкую производительность почти в отсортированных списках, вставление в правильном положении будет намного быстрее, чем добавление в конце и затем обращение он; и сортировка слиянием не могла бы быть никакой опцией для Вас, поскольку, возможно, требовалось бы слишком много внешней памяти, если список огромен. BTW я использовал пользовательскую реализацию сортировки слиянием, это только, использует 1/2 внешнего устройства хранения данных к наивной реализации (которому нужно столько же внешнего устройства хранения данных сколько сам размер массива).

, Если сортировка слиянием не является никакой опцией и quicksort, не никакая опция наверняка, лучшая альтернатива является, вероятно, пирамидальной сортировкой.

Мои результаты: Добавление новых элементов просто в конце и затем обращении массив было несколькими величинами быстрее, чем вставка их в правильном положении. Однако мой начальный массив имел 10 (отсортированных) элементов mio, и я добавлял другой (неотсортированный) mio. Таким образом, если Вы добавляете, что 10 элементов к массиву 10 mio, вставляя их правильно намного быстрее, чем обращение всего. Таким образом, ответ на Ваш вопрос также зависит от того, насколько большой (отсортированный) массив начальной буквы и сколько новых элементов Вы хотите добавить к нему.

Необходимо добавить их прежде и затем использовать вид основания, это должно быть оптимально

http://en.wikipedia.org/wiki/Radix_sort#Efficiency

Если это-.NET, и объекты являются целыми числами, это более быстро для добавления их к Словарю (или если Вы находитесь на.Net 3.0 или выше использования HashSet, если Вы не возражаете терять дубликаты), Это дает Вам автоволшебную сортировку.

я думаю, что строки работали бы тот же путь также. Красавица - Вы, получают O (1) вставка и сортирующий этот путь.

Вставка объекта в отсортированный список берет O(n) время, не O(log n) время. Необходимо найти, что место помещает его, беря O(log n) время. Но тогда необходимо сместиться по всем элементам - взятие O(n) время. Так вставка при поддержании отсортированного мыса O(n ^ 2), где как вставка их всех и затем сортировка O(n log n).

В зависимости от Вашей реализации вида, можно стать еще лучше, чем O(n log n), если количество вставок намного меньше, чем размер списка. Но если это так, это не имеет значения так или иначе.

Также - вставка все и решение для вида, если количество вставок является большим, иначе оно, вероятно, не будет иметь значения.

На высоком уровне это - довольно простая проблема, потому что можно думать о сортировке, как просто выполнено с помощью итераций поиска. Когда Вы хотите вставить элемент в заказанный массив, список или дерево, необходимо искать точку, в которой можно вставить его. Тогда Вы вставляете его по, надо надеяться, низкой цене. Таким образом, Вы могли думать об алгоритме сортировки как о просто взятии набора вещей и, один за другим, поиск надлежащего положения и вставка их. Таким образом вид вставки (O (n* n)) является выполненным с помощью итераций линейным поиском (O (n)). Дерево, "куча", слияние, основание и быстрая сортировка (O (n*log (n))) могут считаться выполненным с помощью итераций двоичным поиском (O (журнал (n))). Возможно иметь O (n) вид, если базовый поиск является O (1) как в заказанной хэш-таблице. (Пример этого сортирует 52 карты путем бросания их в 52 мусорных ведра.)

, Таким образом, ответ на Ваш вопрос, вставляя вещи по одному, по сравнению с коплением их, и затем сортировка их не должна иметь большого значения в большом-O смысле. У Вас могли, конечно, быть постоянные множители для контакта с, и те могли бы быть значительными.

, Конечно, если n является маленьким, как 10, целое обсуждение глупо.

Вставка объекта в отсортированный список является O (зарегистрируйте n), в то время как сортировка списка является O (n, регистрируют N), Который предположил бы, что всегда лучше отсортировать сначала и затем вставить

, Но remeber крупный 'O' только касается масштабирования скорости с количеством объектов, могло бы случиться так, что для Вашего приложения вставка в середине является дорогой (например, если это был вектор), и таким образом добавляя, и сортирование позже могло бы быть лучше.

Если Вы добавляете в наборах, можно использовать сортировку слиянием. Отсортируйте список объектов, которые будут добавлены, затем скопируют с обоих списков, сравнивая объекты для определения, какой копируется затем. Вы могли даже скопировать оперативный, если изменяют размеры Вашего целевого массива и работы от конца назад.

эффективность этого решения является O (n+m) + O (m, регистрируют m), где n является размером исходного списка, и m является количеством вставляемых объектов.

Редактирование: , Так как этот ответ не получает любви, я думал, что буду конкретизировать его с некоторым примером кода C++. Я предполагаю, что отсортированный список сохранен в связанном списке, а не массиве. Это изменяет алгоритм для больше сходства на вставку, чем слияние, но принцип является тем же.

// Note that itemstoadd is modified as a side effect of this function
template<typename T>
void AddToSortedList(std::list<T> & sortedlist, std::vector<T> & itemstoadd)
{
    std::sort(itemstoadd.begin(), itemstoadd.end());
    std::list<T>::iterator listposition = sortedlist.begin();
    std::vector<T>::iterator nextnewitem = itemstoadd.begin();
    while ((listposition != sortedlist.end()) || (nextnewitem != itemstoadd.end()))
    {
        if ((listposition == sortedlist.end()) || (*nextnewitem < *listposition))
            sortedlist.insert(listposition, *nextnewitem++);
        else
            ++listposition;
    }
}

(Если список, о котором Вы говорите, похож на C# List<T>.) Добавляющий некоторые значения к правильным положениям в отсортированный список со многими значениями собирается потребовать меньшего количества операций. Но если количество добавляемых значений станет большим, оно потребует больше.

я предложил бы использовать не список, но некоторую более подходящую структуру данных в Вашем случае. Как двоичное дерево, например. Отсортированная структура данных с минимальным временем вставки.