У меня есть массив строк, содержащих неупорядоченные последовательные числа (от 0 до n), например. [7a, 1b, 2c, 0d, 6e, 5f, 3g, 4h]
, и я хочу записать числа в порядке в файл.записывать несортированный массив последовательных строк, отсортированный в файл эффективно
После того, как, например:
0d
1b
2c
3g
4h
5f
6e
7a
Строка не все имеют одинаковую длину.
Я пытался найти способ сделать это как быстро, так и не занимая слишком много места. Я нашел способ, которым я могу это сделать в O (n) пространственной сложности и O (n) производительности: я создаю массив с n ячейками и вставляю каждую строку в свой номер ячейки.
for (i = 0; i < n; i++)
sortedArray[originalArray[i]] = originalArray[i]
... что-то вроде этого (создание нового массива размером исходного и заполнить его в один проход), а затем с другой цикл записать содержимое отсортированного массива в файл.
Но я ищу лучший способ сделать это.
Что такое «лучше»? Космическая сложность? Сложность времени? Временная сложность компрометирует пространство? Пространство, компромиссное время? –
Что произойдет, если ваше n равно 2^32 или 2^64? Если у вас есть массив из 10 ячеек со значениями от 0 до 2^16, вам все равно потребуется 2^16 операций для распечатки «отсортированного» массива. Вы можете потребовать свой алгоритм O (n), но это действительно не так. – Tim3880
Можем ли мы перефразировать этот вопрос на «как отсортировать такой массив»? Поскольку файл IO вызывает много вопросов. –