python bisect.insort (список, значение)

Question

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

Любая помощь будет высоко ценится.

Answer 1

Эта вставка value в list в правильном положении, обратите внимание, что предполагается, что она уже отсортирована.Из документации:

Вставьте x в отсортированном порядке.Это эквивалентно a.insert(bisect.bisect_left(a, x, lo, hi), x) при условии, что a уже отсортировано.Помните, что в поиске O (log n) преобладает медленный шаг вставки O (n).

Последняя часть относится к тому факту, что вставка в список Python равна O(n).Поиск выполняется с использованием бинарный поиск .

Если вы начинаете с пустого списка и неоднократно используете этот алгоритм для вставки объектов в список, окончательный список будет отсортирован.Этот алгоритм известен как двоичная сортировка вставок .Например:

import bisect

l = [1, 3, 7, 5, 6, 4, 9, 8, 2]

result = []
for e in l:
    bisect.insort(result, e)

print(result)

Вывод

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Примечание: Сложность этого алгоритма составляет O(n*n) с учетом O(n)шаг вставки.