Чувак, у меня в последнее время немного кружится голова, как насчет тебя. Ну, если честно, я не думаю, что чтение о сортировке излечит вашу болезнь.
Я думаю, что первое, что следует рассмотреть, это два способа сортировки данных: первый будет основан на сравнении, а второй не будет основан на сравнении. В поле на основе сравнения у нас есть алгоритмы сортировки, такие как пузырьковая сортировка, сортировка вставками, сортировка слиянием и многое другое. При сортировке, не основанной на сравнении, следует отметить только сортировку по основанию и сортировку по счету. Поскольку можно сделать вывод, что сортировка на основе сравнения сравнивает два разных объекта и упорядочивает их таким образом, чтобы они имели заданный шаблон, и поскольку можно сделать вывод, что сортировка без сравнения не сравнивает два объекта.
Во-первых, я скажу, что для интервью, я считаю, что, скорее всего, будет достаточно знать один алгоритм сортировки на основе сравнения, подсчета и сортировки по основанию, а затем, возможно, понять крах определенных алгоритмов сортировки, например, с быстрой сортировкой, имеющей наихудший случай. O (n²).
Сортировка слиянием:
Временная сложность → O (n log (n))
Космическая сложность → O(1)
Алгоритм сортировки на основе сравнения, который я решил понять, был сортировкой слиянием. Сортировка слиянием работает по принципу «разделяй и властвуй». Это рекурсивная функция, которая делит содержимое на два подмассива, а затем до тех пор, пока в массиве не останется только один фрагмент данных. Затем после этого левый подмассив сравнивается с правым, а затем упорядочивается с массивом, который сформировал подмассивы. Все это делается на месте. На практике вы беретесь за эту ветвь за раз, пока она не будет завершена, это означает своего рода методологию «сначала в глубину». Следует также помнить о компромиссе с пространством, поскольку рекурсивная функция создает n вызовов в стеке. Это по сравнению с другими алгоритмами, такими как пузырьковая сортировка, сортировка выбором и сортировка вставками, которые являются O (n²) по времени, но O (1) по пространству.
Сортировка подсчета:
Временная сложность → O (n + k)
Пространственная сложность → O(n + k)
Сортировка подсчетом хорошо работает для небольших массивов и получила свое название от подсчета вхождений каждой сущности в массиве. Делая это, вы, по сути, имеете начальный индекс для каждого числа или место, где первый индекс каждого объекта должен быть соответственно помещен в пустой массив. Однако, чтобы сделать это стабильным решением, вам нужно пройтись по массиву, и каждый раз, когда вы сталкиваетесь с объектом определенного типа, вы добавляете его в место, которое ему было назначено. Затем вы увеличиваете позицию, в которой будет следующее вхождение того же типа, на единицу. Это делает так, что в следующий раз, когда встречается массив этого типа, он добавляется справа от первого экземпляра этого конкретного типа. Это делает сортировку стабильной, поскольку первый экземпляр всегда находится в том порядке, в котором он был обнаружен.
Сортировка по основанию:
Временная сложность → O (d (n + b))
Сортировка по основанию — это, по сути, более продвинутый алгоритм сортировки с подсчетом, который может применяться к большим базовым числам, исчисляемым сотнями. Он начинает с реализации сортировки подсчетом на десятках и соответственно сортирует их, а затем сортирует на сотнях и так далее. Когда у него заканчиваются места, он заменяет значение 0, пока не будет достигнуто самое большое место массива. Интересная вещь с сортировкой по основанию заключается в том, что сложность времени и пространства также легко поддается податливости. Это происходит путем изменения базы, так как с более низкой базой у вас более медленная временная сложность, но вы используете меньше места. Здесь компромисс должен быть очень тщательно проанализирован. Поскольку сортировка по основанию зависит от размера и входных данных массива, следует также проанализировать, будет ли лучшим решением сортировка по основанию или другая сортировка сравнения O (n log (n)).
Что ж, ребята, не знаю, как вам, а мне нужно сделать перерыв в подготовке к собеседованию, поэтому завтра мы собираемся пройтись по новой территории и посмотреть на новаторские инновации в мире технологий. Тогда увидимся!
Источники:
