Какие алгоритмы сортировки вы знаете?

Основные алгоритмы сортировки, с которыми я знаком:

1. Сортировка пузырьком (Bubble Sort). Простая реализация, но низкая эффективность (O(n^2)).
2. Сортировка выбором (Selection Sort). Тоже простая, O(n^2), но делает меньше обменов, чем пузырьковая.
3. Сортировка вставками (Insertion Sort). Эффективна для почти отсортированных данных или малых наборов (O(n^2) в худшем случае, O(n) в лучшем).
4. Сортировка слиянием (Merge Sort). Алгоритм "разделяй и властвуй", стабильный, средняя и худшая сложность O(n log n). Требует дополнительной памяти O(n).
5. Быстрая сортировка (Quick Sort). Еще один алгоритм "разделяй и властвуй", обычно самый быстрый на практике (средняя сложность O(n log n)), но в худшем случае O(n^2). Нестабильный.
6. Пирамидальная сортировка (Heap Sort). Использует структуру данных "куча". Сложность O(n log n), не требует дополнительной памяти (in-place). Нестабильный.

Python поддерживает несколько встроенных алгоритмов сортировки, которые оптимизированы и используются функцией sorted() и методом списков .sort(). Обычно это Timsort – гибридный алгоритм, сочетающий сортировку слиянием и сортировку вставками, очень эффективный на реальных данных.

Вот пример реализации пузырьковой сортировки:

def bubble_sort(arr):
    n = len(arr)
    # Проходим по всем элементам массива
    for i in range(n):
        # flag для оптимизации, если перестановок не было - массив отсортирован
        swapped = False
        # Последние i элементов уже на своих местах
        for j in range(0, n - i - 1):
            # Проходим по массиву от 0 до n-i-1
            # Если текущий элемент больше следующего, меняем их местами
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # Если за проход не было перестановок, массив отсортирован
        if not swapped:
            break
    return arr

# Пример использования
# my_list = [64, 34, 25, 12, 22, 11, 90]
# bubble_sort(my_list)
# print("Отсортированный массив:", my_list)

Выбор алгоритма зависит от требований: размера данных, необходимости стабильности, наличия дополнительной памяти и степени предварительной отсортированности данных. В большинстве случаев в Python используются встроенные методы из-за их оптимизации.