Каков наилучший алгоритм сортировки в этой ситуации?

Question

myarray = empty
n = 10000
range = 1000
loop 1 to n {
    x = random number between 1 and range 
    if x not in myarray {
        add x to myarray
        sort myarray
        do something 
    }
}

Я рассмотрел сортировку вставкой, но для этого потребовалось бы смещение элементов.И быстрая сортировка была бы плохой в уже отсортированных списках.Лучшее, что я мог придумать сейчас, это Min Heap.Есть какой-то менее известный алгоритм сортировки, который лучше подходит для этой ситуации?Это в C ++ STL?

Answer 1

Вы ищете std::set. Он сохраняет сортировку при вставке и позволяет быстро выполнить операцию «не в».

Answer 2

самый лучший вариант , когда вы знаете, что сортируемые вами числа всегда будут между 0 и max_value равны Подсчет сортировки , с непревзойденной сложностью: O(n).

Answer 3

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

Поскольку вас интересуют операции

• Вставка элемента
• Проверка наличия элемента
• Поддержание порядка сортировки

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

Надеюсь, это поможет!