Рубрики

Алгоритмы | Сортировка | Вопрос 5

Дан несортированный массив. Массив обладает таким свойством, что каждый элемент в массиве находится на расстоянии не более k от своей позиции в отсортированном массиве, где k — положительное целое число, меньшее размера массива. Какой алгоритм сортировки можно легко изменить для сортировки этого массива и какова сложность времени?
(A) Сортировка вставкой с временной сложностью O (kn)
(B) Сортировка кучи с временной сложностью O (nLogk)
(C) Быстрая сортировка с временной сложностью O (kLogk)
(D) Объединить сортировку с временной сложностью O (kLogk)

Ответ: (Б)
Объяснение: см. Http://espressocode.top/nearly-sorted-algorithm/ для объяснения и реализации.
Тест на этот вопрос

Рекомендуемые посты:

Алгоритмы | Сортировка | Вопрос 5

0.00 (0%) 0 votes