алгоритм сортировки подходит для отсортированного списка

Question

У меня есть отсортированный список под рукой.Теперь я добавляю новый элемент в конец списка.Какой алгоритм сортировки подходит для такого сценария?

Быстрая сортировка имеет наихудшую временную сложность O (n ² ), когда список уже отсортирован.Означает ли это, что временная сложность, если в указанном выше случае используется быстрая сортировка, будет близка к O (n ² )?

Answer 1

Если вы добавляете только один элемент, найдите место, куда он должен быть вставлен, и поместите его туда.Для массива вы можете выполнить бинарный поиск по времени O (logN) и вставить в O (N).Для связанного списка вам нужно выполнить линейный поиск, который займет O (N) времени, но затем вставка будет O (1).

Что касается вашего вопроса о быстрой сортировке: если вы выберете первое значениекак ваш опорный пункт, тогда да, это будет O (N ² ) в вашем случае.Выберите случайный круг, и ваш случай все равно будет в среднем O (NlogN).Однако способ, который я предлагаю выше, проще и быстрее в вашем конкретном случае.

Answer 2

Вместо добавления в конец списка вы должны выполнить операцию insert.

То есть, добавляя 5 к [1,2,3,4,7,8,9], вы захотите «вставить», поместив его туда, где он должен быть в отсортированном списке, а не в конце, а затем заново отсортировав весь список.

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

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

Answer 3

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

Answer 4

Что именно вы подразумеваете под «списком»? Вы имеете в виду, в частности, связанный список или просто некоторую линейную (последовательную) структуру данных, например, массив?

Если это связанный список, вам потребуется линейный поиск правильной позиции. Сама вставка может быть сделана в постоянное время.

Если это что-то вроде массива, вы можете добавить в конец и отсортировать, как вы уже упоминали. Сортированная коллекция плоха для быстрой сортировки, только если она действительно плохо реализована. Если вы выберете свою опору с типичным медианой 3 алогрита, отсортированный список даст оптимальную производительность.

Answer 5

Я предполагаю, что вы используете массив, так как вы говорите о быстрой сортировке, поэтому просто добавление элемента потребовало бы найти место для его вставки (O (log n)), а затем фактически вставить его (O (n) ) на общую сумму O (n). Просто добавив его в конец, а затем прибегнув к полному списку, определенно не тот путь.

Однако, если это будет частая операция (т. Е. Если вам нужно будет добавлять элементы при сохранении отсортированного свойства), то вы будете платить O (n ^ 2) за добавление еще n элементов в список. Если вы измените свое представление на сбалансированное двоичное дерево, оно упадет до O (n log n) для других n вставок, но поиск элемента по индексу станет O (n). Если вам никогда не нужно этого делать, а просто перебирайте элементы по порядку, дерево определенно поможет.

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