В Python популярны несколько алгоритмов сортировки, каждый с разной сложностью и применением: - **Сортировка пузырьком (Bubble Sort)** Простой, но неэффективный (O(n²)). ``` def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] ``` - **Быстрая сортировка (Quick Sort)** Рекурсивный, в среднем O(n log n). ``` def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort(left) + middle + quick_sort(right) ``` - **Сортировка слиянием (Merge Sort)** Устойчивый, O(n log n), но требует доп. памяти. ``` def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) ``` - **Timsort** (встроенный в Python) Гибридный (слияние + вставки), O(n log n) в худшем случае. Используется в `sorted()` и `list.sort()`. Для небольших данных подойдут простые методы, для больших — Quick Sort или Timsort.