Алгоритмы сортировки для начинающего

Question

Итак, .Net и Java избаловали меня тем, что я «не обязан» изучать какие-либо алгоритмы сортировки, но теперь мне нужно отсортировать массив на разных языках, в которых нет такой роскоши. Я смог разобраться с сортировкой пузырьков без особых проблем. Тем не менее, некоторые источники ненавидят использование пузырьковой сортировки из-за ужасной производительности со средним и худшим сценарием из n ^ 2 сравнений. Похоже, что пузырьковая сортировка справилась с задачей, но насчет массива, который содержит +100 000 элементов, и я беспокоюсь, что производительность может быть проблемой на этом уровне. С другой стороны, некоторые другие алгоритмы выглядят довольно пугающими с точки зрения сложности. Мой вопрос: Что было бы хорошим продолжением после пузырьковой сортировки с точки зрения лучшей производительности, но не уходило в сложную пустошь при реализации?

Как примечание, я аналитик, что программы по мере необходимости, а не майор CS. Излишне говорить, что есть некоторые пробелы, которые я еще заполнил в своем опыте программирования. Спасибо:)

Answer 1

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

• Быстрая сортировка хорошая, но вы можете столкнуться с проблемами с памятью.
• Я использовал Heapsort с большим успехом, но он не гарантированно стабилен (хотя у меня никогда не было проблем).
• Bogosort интересно реализовать и говорить, но совершенно непрактично.
• и т. Д. *

Хорошее понимание данныхсортировка помогает решить, какой алгоритм лучше.Например:

• Насколько большим будет массив?
• Есть ли вероятность, что он уже отсортирован или частично отсортирован?
• Какие данные содержит массив?
• Насколько сложно / дорого сравнить два элемента в массиве?
• Насколько сложно / дорого определить, отсортирован ли массив?
• и т. Д....

Не существует одного алгоритма сортировки, который был бы лучше, чем все остальные.Выбор того, что соответствует вашим потребностям, - это то, что вы подберете со временем и с практикой.

Answer 2

Не торопитесь, чтобы изучить Quicksort, это отличный алгоритм и не такой сложный, если вы идете медленно.

Если вы хотите, чтобы некоторые алгоритмы сортировки просто намокали (тер), я бы порекомендовал Insertion Sort и Selection Sort, они, как правило, лучше, чем Bubble Sort, и быстрые для понимания и реализации. Сортировка слиянием также распространена в алгоритмах. Тем не менее, вам будет намного удобнее использовать быструю сортировку.

Вы также должны понимать разницу между стабильной и нестабильной сортировкой, если вы этого еще не сделали. Стабильная сортировка не изменит порядок элементов с тем же ключом, в то время как нестабильная может.