Сложность сортировки

Question

Дано массив, в котором значения в четных индексах инкрементны, а значения в нечетных индексах находятся в декрементальном порядке. Например:

[1,99,16,65,45,23,97] 

Я думал о двух различных способов сортировки это:

1. Начиная с я = 0, у = a.length-2 и сравнивающие значения а [я] с [j]. i + = 2, если a [i] меньше или j = 2, если a [j] меньше. Для этого нужен дополнительный массив. Время равно O (n), а пространство O (n).

2. Реверсирование порядка элементов, где их индекс является нечетным, а затем пузырь сортировать весь массив. Пространство - это O (1) .. как насчет времени?

Какая эффективность? Какова наихудшая временная и пространственная сложность для каждого? Сорт пузыря может занять много времени, нет?

Answer 1

Мне еще предстоит увидеть хороший вариант использования для создания пузырей в реальном мире. Если вы перейдете к варианту 2, как только вы переверните ячейки в нечетных индексах, у вас будет массив, который может сортироваться или не сортироваться по своему усмотрению, и примените тип пузырьков O (n). Тривиальным улучшением было бы использовать сортировку quicksort или merge и получить сложность времени O (n log (n)).