Вставка числа в сортированный массив!
Я хотел бы записать часть кода для вставки числа в сортированный массив в соответствующем положении (т.е. массив должен все еще остаться отсортированным после вставки),
Моя структура данных не позволяет дубликаты.
Я планирую сделать что-то вроде этого:
- Найдите правильный индекс, куда я должен помещать этот элемент с помощью двоичного поиска
- Создайте пространство для этого элемента путем перемещения всех элементов от того индекса вниз.
- Поместите этот элемент там.
Есть ли какой-либо другой лучший путь?
3 ответа
Если у вас действительно есть массив, а не лучшая структура данных, это оптимально. Если у вас есть гибкость в реализации, взгляните на AA Trees - они довольно быстрые и простые в реализации. Очевидно, что занимает больше места, чем массив, и это не стоит того, если количество элементов недостаточно велико, чтобы заметить медлительность блита по сравнению с магией указателя.
Нужно ли все время полностью сортировать данные? В противном случае, если необходимо быстро получить доступ только к наименьшему или наибольшему элементу, Двоичная куча дает постоянное время доступа и время добавления и удаления для входа в систему. Более того, это может удовлетворить ваше условие, что память должна быть последовательной, так как вы можете реализовать BinaryHeap поверх массива (то есть, левый дочерний элемент array [2n + 1], правый дочерний элемент array [2n + 2]).
Реализация дерева на основе кучи будет более эффективной, если вы вставляете много элементов - log n для операций поиска / удаления и вставки.