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

1. Быстрая сортировка.
   Быстрая сортировка — широко используемый алгоритм сортировки, известный своей эффективностью. Он следует подходу «разделяй и властвуй», при котором массив разбивается на части и рекурсивно сортируется подмассивы. Быстрая сортировка имеет среднюю и наилучшую временную сложность O(n log n), а временную сложность наихудшего случая — O(n^2).

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    smaller, equal, larger = [], [], []
    for num in arr:
        if num < pivot:
            smaller.append(num)
        elif num == pivot:
            equal.append(num)
        else:
            larger.append(num)
    return quicksort(smaller) + equal + quicksort(larger)

1. Сортировка слиянием.
   Сортировка слиянием — еще один эффективный алгоритм сортировки, основанный на подходе «разделяй и властвуй». Он делит массив на две половины, рекурсивно сортирует их, а затем объединяет отсортированные половины. Сортировка слиянием во всех случаях имеет постоянную временную сложность 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)
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

3. Групповая сортировка.
   Групповая сортировка – это алгоритм сортировки на месте, в котором используется структура данных двоичной кучи. Он начинается с построения кучи из массива, а затем неоднократно извлекает из кучи максимальный элемент и помещает его в конец массива. Во всех случаях временная сложность пирамидальной сортировки равна O(n log n).

def heapsort(arr):
    build_max_heap(arr)
    for i in range(len(arr) - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        max_heapify(arr, index=0, size=i)
    return arr
def build_max_heap(arr):
    for i in range(len(arr) // 2 - 1, -1, -1):
        max_heapify(arr, index=i, size=len(arr))
def max_heapify(arr, index, size):
    largest = index
    left = 2 * index + 1
    right = 2 * index + 2
    if left < size and arr[left] > arr[largest]:
        largest = left
    if right < size and arr[right] > arr[largest]:
        largest = right
    if largest != index:
        arr[index], arr[largest] = arr[largest], arr[index]
        max_heapify(arr, largest, size)

4. Сортировка подсчетом.
   Сортировка подсчетом — это алгоритм сортировки без сравнения, который лучше всего работает, когда известен диапазон входных значений. Он подсчитывает частоту каждого отдельного элемента во входном массиве, а затем использует эту информацию для построения отсортированного выходного массива. Сортировка по счету имеет временную сложность O(n + k), где k — диапазон входных значений.

def counting_sort(arr):
    max_value = max(arr)
    count_array = [0] * (max_value + 1)
    for num in arr:
        count_array[num] += 1
    sorted_array = []
    for i in range(len(count_array)):
        sorted_array.extend([i] * count_array[i])
    return sorted_array

В этой статье мы рассмотрели несколько алгоритмов сортировки с наименьшей временной сложностью. Быстрая сортировка и сортировка слиянием обеспечивают среднюю и наилучшую временную сложность O(n log n), а пирамидальная сортировка и сортировка подсчетом также обеспечивают эффективную временную сложность. Каждый алгоритм имеет свои уникальные характеристики, и выбор алгоритма сортировки зависит от конкретных требований решаемой задачи.