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

Популярные алгоритмы сортировки:

1. Bubble Sort – простой, но неэффективный (O(n²)).

   python

   Копировать

   def bubble_sort(arr):
       for i in range(len(arr)):
           for j in range(len(arr)-1):
               if arr[j] > arr[j+1]:
                   arr[j], arr[j+1] = arr[j+1], arr[j]

2. Merge Sort – стабильный, рекурсивный (O(n log n)).

   python

   Копировать

   def merge_sort(arr):
       if len(arr) > 1:
           mid = len(arr)//2
           L, R = arr[:mid], arr[mid:]
           merge_sort(L)
           merge_sort(R)
           i = j = k = 0
           while i < len(L) and j < len(R):
               if L[i] < R[j]:
                   arr[k] = L[i]
                   i += 1
               else:
                   arr[k] = R[j]
                   j += 1
               k += 1
           arr[k:] = L[i:] or R[j:]

3. Quick Sort – эффективный (O(n log n) в среднем, O(n²) в худшем).

   python

   Копировать

   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)

4. Heap Sort – на основе бинарной кучи (O(n log n)).

5. Insertion Sort – эффективен для почти отсортированных данных (O(n²)).

Выбор алгоритма зависит от данных: размер, степень упорядоченности, требования к памяти.