В java, каков наилучший способ сортировки целочисленного массива, если смещен только последний элемент числа?

Question

Это массив целых чисел.Он был создан таким образом: ни один элемент не повторяется.Каждый раз, когда элемент добавляется, его номер является следующим доступным целым числом, начиная с 0.Таким образом, если вы добавите 6 элементов в ряд, они будут 0, 1, 2, 3, 4, 5 в указанном порядке.Если вы удаляете элемент, массив сжимается, и между двумя элементами остается «дыра», они перестают быть последовательными из-за этого разрыва: 0, 1, 3, 4, 5. Тогда возникает проблема: если выдобавить новый элемент, он добавляется в конец, но имеет следующее доступное целое число.Итак, массив теперь равен 0, 1, 3, 4, 5, 2. Его нужно отсортировать, чтобы 2 могло занимать свое место между 1 и 3. Каков наилучший способ сделать это?Я подумал о нескольких методах.Список почти упорядочен, и у него есть свойство, что при упорядочении каждый элемент равен или больше, чем его индекс в массиве.В настоящее время я делаю пузырьковую сортировку (не смейтесь), я думаю, что быстрая сортировка излишня, я не хочу использовать рекурсивную или использовать временные массивы, и я не хочу менять метод add-element (который добавляет элемент вконец), поэтому он должен быть отсортирован сразу после добавления элемента (поэтому только последний элемент не на своем месте)

Answer 1

Возьмите последний элемент и выполните сортировку вставки .

Answer 2

Может быть, вам стоит взглянуть на идею Сортировка вставок .

Answer 3

Вам не нужно сортировать весь список, просто вставьте последний элемент по порядку:

int pos = array.length - 1:
while (pos > 0 && array[pos] < array[pos - 1]) {
    tmp = array[pos - 1];
    array[pos - 1] = array[pos];
    array[pos] = tmp;
    pos--;
}

Answer 4

А как насчет использования java.util.BitSet вместо этого?Вы получите вставку и удаление в постоянном времени (хотя поиск первого свободного места все равно займет O (n)).А с nextSetBit вы можете перебирать наборы в порядке возрастания.С помощью nextClearBir () поиск первого неиспользуемого индекса также становится тривиальным.

Answer 5

Вы ограничены в использовании массива?Если нет, то просто используйте TreeSet .Зачем писать свой собственный алгоритм сортировки, если вы можете использовать стандартные библиотеки, которые уже выполняют эту функцию?Гарантированное время O (log (n)) для вставок.

import java.util.TreeSet;

TreeSet<Integer> sortedSet = new TreeSet<Integer>();
// Add integers as needed
sortedSet.add( someInt );
// If you need an array at the end
Integer[] array = sortedSet.toArray( new Integer[sortedSet.size()] );

Answer 6

//based on gpeche's code
int pos = array.length - 1;
int val = array[pos];
while (pos > 0 && array[pos-1] > val) {
    array[pos] = array[pos - 1];
    pos--;
}

array[pos] = val;