Использование функции сортировки для численного сортировки

Question

Предположим, что у меня есть "Oracle", который сортирует следующим образом:

1, 3, 2000, 11, 17, 20

Становится

1, 11, 17, 20, 2000, 3

(Я не называю этот механизм). Это похоже на команду UNIX sort (без -n).

I remember Windows used to sort filenames like this prior to Windows XP

---

Теперь у меня есть куча чисел и это sort оракула, и я хочу, чтобы сортировать числа численно, как можно предварительно обработать эти числа такие, что sort оракул возвращает правильный порядок ,

Итак, есть функция f(), которая принимает в этих чисел таких, что

рода F ([1,3,2000,11,17,20])

вернет правильный порядок.

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

Answer 1

Это называется lexicographical sort. Вы можете заполнить номера 0, так что все они имеют одинаковое количество цифр, чтобы заставить его вести себя как числовая сортировка. Например, используйте код формата %04d с printf.

Answer 2

1. Сортируйте числа, используя эту функцию сортировки «оракул», в результате чего список чисел называется, например: L.
2. Удалить все однозначное число от L, в результате чего в списке чисел L1, и создать новый список номеров с одной цифрой в том же порядке, как они были в L, в результате чего в списке чисел S (если в L нет однозначных цифр, S будет пустым).
3. Удалить все двузначные числа от L1, в результате чего в списке чисел L2, и добавить двузначные числа в том же порядке, в котором они находились L1 к S (если нет двузначных чисел в L, L1 остается таким же, как L, и число не добавляется к S).
4. ...
5. Удалите все n-значные числа от Ln-1, в результате получим пустой список чисел и добавьте n-значные числа в том же порядке, что и в Ln-1, до S.
6. S В настоящее время S содержит численный список номеров, используя только функцию сортировки «оракул» и функцию, которая возвращает количество цифр числа, которое, мы надеемся, имеет ваша система.

Конечно, вам не нужно, чтобы создать новый список номеров Lk, как вы удалите все к-значные номера от Lk-1 если «оракул» отсортирован список L является изменяемым.