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

Содержание:

1. Введение
2. Сортировка выбором
3. Пузырьковая сортировка
4. Сортировка вставками
5. Сортировка слиянием
6. Быстрая сортировка
7. Кучная сортировка
8. Поразрядная сортировка
9. Сортировка по подсчету
10. Заключение

Сортировка выбором.
Сортировка выбором — это простой алгоритм сортировки, который работает путем многократного поиска минимального элемента из неотсортированной части массива и помещения его в начало. Вот пример реализации на Python:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]

Пузырьковая сортировка.
Пузырьковая сортировка – это алгоритм, основанный на сравнении, который неоднократно меняет местами соседние элементы, если они находятся в неправильном порядке. Вот пример реализации на Python:

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]

Сортировка вставками.
Сортировка вставками — это простой алгоритм сортировки, который создает окончательный отсортированный массив по одному элементу за раз. Он эффективен для небольших наборов данных или почти отсортированных массивов. Вот пример реализации на Python:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Сортировка слиянием.
Сортировка слиянием — это алгоритм «разделяй и властвуй», который делит массив на две половины, сортирует их рекурсивно, а затем объединяет отсортированные половины. Вот пример реализации на Python:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]

        merge_sort(left)
        merge_sort(right)

        i = j = k = 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

Быстрая сортировка.
Быстрая сортировка — это алгоритм «разделяй и властвуй», который выбирает опорный элемент и разбивает массив на более мелкие и более крупные элементы. Затем он рекурсивно сортирует меньшие и большие элементы. Вот пример реализации на Python:

def quick_sort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)
def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

Кучная сортировка.
Кучная сортировка — это алгоритм сортировки на основе сравнения, который использует структуру данных двоичной кучи для сортировки элементов. Сначала он создает максимальную кучу из массива, а затем неоднократно извлекает максимальный элемент и перестраивает кучу. Вот пример реализации на Python: