Сортировать «отсортированный» массив

Question

1. Предположим, задан массив размера n с отсортированными значениями.
2. На итерации i дается новое случайное значение, которое вставляется в конец массива.
3. Затем массив восстанавливается и отбрасывает элемент наименьшего значения.
4. После итерации n сохраненный массив будет содержать элементы с наибольшим значением.

Например, в синтаксисе Java это будет что-то вроде:

List l = new ArrayList();
l.add(new Integer(2));
l.add(new Integer(3));
l.add(new Integer(6));
l.add(new Integer(9));

Random rand = new Random();
for (int i=0; i < n; i++) {
  l.add(new Integer(rand.nextInt(1000)));
}    
Collections.sort(l);
l.remove(0);

Но, похоже, это неэффективно. Есть лучший алгоритм?

Answer 1

Вы можете использовать бинарный поиск, чтобы вставить значение в отсортированный массив.

Answer 2

Вот еще одно решение, которое объединяет операции в просто поиск, копию массива и набор значений. Это позволяет избежать необходимости сортировки или зацикливания.

public static <T extends Comparable<T>> 
        void insertAndRemoveSmallest(T[] array, T t) {
    int pos = Arrays.binarySearch(array, t);
    if (pos < 0) pos = ~pos;
    // this is the smallest entry so no need to add it and remove it.
    if (pos == 0) return;
    pos--;
    // move all the entries down one.
    if (pos > 0) System.arraycopy(array, 1, array, 0, pos);
    array[pos] = t;
}

Эта программа

public static void main(String... args) {
    Integer[] ints = {2, 3, 7, 6, 9};
    System.out.println("Starting with " + Arrays.toString(ints));
    for (int i : new int[]{5, 1, 10, 8, 8}) {
        insertAndRemoveSmallest(ints, i);
        System.out.println("After adding " + i + ": " + Arrays.toString(ints));
    }
}

печать

Starting with [2, 3, 7, 6, 9]
After adding 5: [3, 5, 7, 6, 9]
After adding 1: [3, 5, 7, 6, 9]
After adding 10: [5, 7, 6, 9, 10]
After adding 8: [7, 6, 8, 9, 10]
After adding 8: [6, 8, 8, 9, 10]

Answer 3

Ключевой вопрос заключается в том, нужно ли вам знать 4 верхних элемента ПОСЛЕ КАЖДОГО НОВОГО ИЗДЕЛИЯ, или вам нужны только 4 верхних после создания всех элементов. Кроме того, это буквально 4 главных предмета, или это просто пример или иллюстрация?

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

Точно так же, если вам нужен только верхний N в конце процесса, может быть быстрее собрать их все, отсортировать и затем взять верхний N. Но, опять же, если большинство значений удаляются, сортировка Относительные позиции «неудачников» могут быть большой тратой времени. Если нам нужна только верхняя четверка, то не имеет значения, является ли элемент №5 или №10,382,842.

Answer 4

Я не уверен, что приведенный выше пример сработает. Что такое n? и если вы будете циклически добавлять случайные числа от 1 до 1000, у вас всегда будут 1000, 999, 998 и 997 - нет? Я не думаю, что добавление # и повторное использование каждый раз является эффективным - вероятно, было бы быстрее проверить каждую из четырех позиций и заменить на более высокое #.

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

Answer 5

Вам действительно нужен онлайн один элемент за раз? Или вы на самом деле анализируете большую коллекцию данных и просто хотите получить верхние n элементов? Если это последнее, посмотрите на частичный qsort .

Answer 6

ShellSort и Natural Mergesort очень производительны (binary search требует гораздо больше времени, так как одно обновление все равно требует O (n).

В качестве альтернативы, вы можете использовать структуры кучи.