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

Question

Я новичок в алгоритмах, поэтому, пожалуйста, прости меня, если это звучит просто или глупо.

Я хочу знать это: вместо добавления данных в какой-то список, а затем выполнения сортировки в списке,есть метод (структура данных + алгоритм), который позволяет мне сортировать данные во время их добавления или, другими словами, вставлять данные на свое место?

например: если я хочу добавитьОт 3 до {1,5,6}, вместо того, чтобы добавлять его в начале или конце и затем сортировать список, я хочу, чтобы «3» следовал после «1» «напрямую».

спасибо

Answer 1

Если вы используете бинарное дерево поиска вместо массива, сортировка произойдет «автоматически», потому что это уже выполняется методом вставки узлов. Таким образом, двоичное дерево всегда сортируется, и его легко пройти. Единственная проблема заключается в том, что когда вы уже (более или менее) отсортировали данные, дерево становится неуравновешенным (именно здесь вступают в игру красно-черные деревья и другие варианты).

Answer 2

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

Answer 3

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

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

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

Answer 4

Существует два основных способа вставки значения в список, которые вы используете, зависит от того, какой тип списка вы используете:

• Используйте бинарный поиск, чтобы найти гдезначение должно быть вставлено, и вставьте туда значение.

• Цикл от конца списка, перемещая все более высокие значения на один шаг вверх, и поместите значение в промежуток перед самым низкимболее высокое значение.

Первый метод обычно используется, если вы используете двоичное дерево или связанный список, когда вам не нужно перемещать элементы в списке, чтобы выполнить вставку.