Сортировка списка элементов по алфавиту, когда у языка нет функции сделать это?

Question

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

Спасибо

Answer 1

В Википедии об этом очень подробно рассказывается: http://en.wikipedia.org/wiki/Sorting_algorithm

В нем содержится длинный список распространенных алгоритмов и информация об их преимуществах и недостатках.

Answer 2

Две части к вопросу:

• как сортировать
• как применить это к алфавитной сортировке в целом (иначе как лексикографическая сортировка).

Два основных типа сортировки, которые наиболее подходят для сортировки по алфавиту:

• a сортировка сравнения , где сравнение сравнивает лексикографически
• MSD radix sort .

Сравнительные сортировки встречаются чаще (отчасти потому, что они более общие в том, что они могут сортировать, отчасти потому, что применение радикальной сортировки к строкам переменной длины немного неудобно по сравнениюс сортировкой осей фиксированной ширины).Можно выбирать из множества компромиссов, но все они рассматривают фактическое сравнение двух элементов как «черный ящик», отдельный от самого алгоритма сортировки.

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

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

Answer 3

В Интернете есть действительно хороший инструмент для такого рода вопросов

Поскольку вы не нашли его, вот хорошая отправная точка: быстрая сортировка

Answer 4

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

Дайте три часа, и вы ознакомитесь с основами. :)

Answer 5

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

Answer 6

Используйте Trie =)