Иногда интервьюеры спрашивают, как сортировать миллион/миллиард 32-битных целых чисел (например, здесь и здесь). Я предполагаю, что они ожидают, что кандидаты сравнивают сортировку O (NLog (N)) с сортировкой radix. Для миллионов целых чисел тип O (NLog (N)), вероятно, лучше, но для миллиарда они, вероятно, одинаковы. Имеет ли смысл?
Как отсортировать (миллион/миллиард/...) целые числа?
Ответ 1
Если у вас возникнет такой вопрос, они не ищут ответа. То, что они пытаются сделать, - это увидеть, как вы думаете о проблеме. Вы прыгаете прямо или задаете вопросы о требованиях к проекту?
Один вопрос, который вам лучше задать, - "Насколько оптимальным решением является проблема?" Может быть, запись в виде пузырей, хранящаяся в файле, достаточно хороша, но вы должны спросить. Задайте вопросы о том, что произойдет, если вход изменится на 64-разрядные номера, если процесс сортировки будет легко обновлен? Спросите, как долго программист должен разработать программу.
Эти типы вопросов показывают мне, что кандидат достаточно мудр, чтобы видеть, что проблема больше, чем просто сортировка чисел.
Ответ 2
Я ожидаю, что они ищут, чтобы вы расширили разницу между внутренней сортировкой и внешняя сортировка. По-видимому, люди сегодня не читают Knuth
Ответ 3
Как сказал aaaa bbbb, это зависит от ситуации. Вы зададите вопросы о требованиях к проекту. Например, если они хотят подсчитать возраст сотрудников, вы, вероятно, используете Сортировка сортировки, я могу сортировать данные в памяти. Но когда данные полностью случайны, вы, вероятно, используете внешнюю сортировку. Например, вы можете разделить данные исходного файла на разные файлы, каждый файл имеет уникальный диапазон (File1 от 0 до 1 м, File2 от 1 м + 1 до 2 м, ect), затем сортировка каждого файла, и, наконец, объединить их в новый файл.
Ответ 4
Это зависит от структуры данных, в которой они хранятся. Сортировка Radix превосходит N-log-N сортировку по довольно небольшим размерам проблем, если вход находится в связанном списке, поскольку ему не нужно выделять какую-либо царапину, и если вы можете позволить распределить буфер нуля размером ввода в начале сортировки, то это же верно для массивов. Это действительно только неправильный выбор (для целых ключей), когда у вас очень ограниченное дополнительное пространство для хранения, а ваш вход находится в массиве.
Я бы ожидал, что точка кроссовера будет значительно ниже миллиона независимо.
Ответ 5
Используйте бит-карту. Для представления целого 32-битного целочисленного диапазона вам потребуется около 500 Мбайт. Для каждого целого числа в заданном массиве просто задается бит, отвечающий за бит. Затем просто сканируйте свою битовую карту слева направо и отсортируйте массив целых чисел.