Хороший алгоритм сортировки наиболее часто отсортированных данных, которые не помещаются в память? [closed]

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

Закрыт 7 лет назад .

В случае, если вам дано:

определенный объем данных
память размером половину размера данных
часть данных сортируется
вы не знаете размер отсортированных данных.

Какой алгоритм сортировки вы бы выбрали? Я спорю между вставкой и быстрой сортировкой. Я знаю, что лучший случай для сортировки вставкой - O (n), но худший - O (n ²). Кроме того, учитывая тот факт, что память ограничена, я бы разделил данные на две части, и для каждой из них выполнял быструю сортировку, а затем объединял все вместе.На разделение данных потребуется O (n) времени, O (n) для объединения данных и O (n log n) для сортировки данных с помощью быстрой сортировки для чистого времени выполнения O (n log n).

Есть ли у кого-нибудь предложения, как это улучшить?

задан templatetypedef 29 February 2012 в 22:08

0 ответов

Другие вопросы по тегам:

java algorithm sorting data-structures space-complexity

Хороший алгоритм сортировки наиболее часто отсортированных данных, которые не помещаются в память? [closed]

0 ответов

Похожие вопросы: