Вставка числа в отсортированный массив!

Question

Я хотел бы написать кусок кода для вставки числа в отсортированный массив в соответствующей позиции (то есть массив должен оставаться отсортированным после вставки)

Моя структура данных не допускает дублирования.

Я планирую сделать что-то вроде этого:

1. Найдите правильный индекс, куда я должен поместить этот элемент, используя бинарный поиск
2. Создайте пространство для этого элемента, переместив все элементы из этого индекса вниз.
3. Поместите этот элемент туда.

Есть ли другой способ лучше?

Answer 1

Если у вас действительно есть массив, а не лучшая структура данных, это оптимально. Если вы гибки в реализации, взгляните на AA Trees - они довольно быстрые и простые в реализации. Очевидно, занимает больше места, чем массив, и это не стоит того, чтобы количество элементов было недостаточно большим, чтобы заметить медлительность блита по сравнению с магией указателя.

Answer 2

Должны ли данные быть отсортированы полностью все время?Если это не так, если требуется только быстрый доступ к наименьшему или наивысшему элементу, Binary Heap дает постоянное время доступа и время добавления и удаления журнала.Более того, это может удовлетворить ваше условие, что память должна быть последовательной, так как вы можете реализовать BinaryHeap поверх массива (т.е. массив [2n + 1] левый потомок, массив [2n + 2] правый потомок).

Answer 3

Реализация дерева на основе кучи была бы более эффективной, если вы вставляете много элементов - введите n для операций поиска, удаления и вставки.