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

1. Пузырьковая сортировка:

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

Время выполнения: в среднем O (n²) и наихудший случай. Память: O (1)

Код Python:

2. Сортировка выбора:

Описание: Найдите наименьший элемент с помощью линейного сканирования и переместите его на передний план (поменяв местами с передним элементом). Затем найдите второй наименьший и переместите его на вторую позицию в списке, снова используя линейное сканирование. Продолжайте делать это, пока список не будет отсортирован.

Время выполнения: в среднем O (n²) и наихудший случай, память: O (1)

Код Python:

3. Сортировка слиянием:

Описание. Сортировка слиянием использует метод "разделяй и властвуй" и представляет собой рекурсивный алгоритм. Хотя его сложнее реализовать, чем другие алгоритмы, он очень эффективен по времени. Он делит список пополам, сортирует каждую из этих половин, а затем объединяет их вместе. К каждой половине применяется одинаковый алгоритм сортировки. Это разделение на половинки продолжается до тех пор, пока вы просто не объедините два списка отдельных элементов.

Время выполнения: среднее значение O (n log (n)) и наихудший случай. Сложность пространства O (n).

Код Python:

4. Быстрая сортировка:

Описание: выберите случайный элемент в качестве точки поворота и разделите список вокруг этого элемента. Все числа, которые меньше, чем элемент поворота, идут слева от точки поворота, а все числа, которые больше элемента поворота, идут справа от точки поворота. Рекурсивно повторяйте разбиение списка и его подсписок, пока список не будет отсортирован. Для этой программы начальный leftIndex == 0 и начальный rightIndex == len (lst) -1.

Временная сложность: O (n log (n)) в среднем и O (n²) наихудший. Память: O (журнал (n)).

Код Python:

Заключение: Итак, у вас есть четыре алгоритма сортировки, которые вам нужно знать, чтобы стать лучшим программистом!