Какие знаешь виды сортировок?

Виды сортировок в программировании

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

Основные категории алгоритмов сортировки

1. Сортировки сравнением (Comparison Sorts)

Эти алгоритмы упорядочивают элементы путем попарного сравнения.

Сортировка пузырьком (Bubble Sort)

• Простейший алгоритм с временной сложностью O(n²)
• Медленный на больших наборах данных, но полезен для обучения

func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

Сортировка вставками (Insertion Sort)

• Эффективен для небольших или почти отсортированных массивов
• Временная сложность: O(n²) в худшем случае, O(n) в лучшем
• Устойчивая сортировка, часто используется как часть более сложных алгоритмов

Сортировка выбором (Selection Sort)

• Находит минимальный элемент и помещает его в начало
• Всегда имеет сложность O(n²), даже для отсортированных данных

2. Эффективные сортировки сравнением

Быстрая сортировка (Quick Sort)

• Разделяй и властвуй алгоритм со средней сложностью O(n log n)
• Неустойчивая сортировка, но обычно самая быстрая на практике
• В Go используется в пакете sort для примитивных типов

func quickSort(arr []int, low, high int) {
    if low < high {
        pi := partition(arr, low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    }
}

Сортировка слиянием (Merge Sort)

• Гарантированная сложность O(n log n) в любом случае
• Устойчивая сортировка, но требует O(n) дополнительной памяти
• Используется в Go для сортировки сложных структур

Пирамидальная сортировка (Heap Sort)

• Сложность O(n log n) в худшем случае
• Не требует дополнительной памяти (in-place)
• Неустойчивая, но с предсказуемой производительностью

3. Сортировки без сравнения (Non-Comparison Sorts)

Сортировка подсчетом (Counting Sort)

• Работает за O(n + k), где k - диапазон значений
• Эффективен когда диапазон значений небольшой

func countingSort(arr []int, max int) []int {
    count := make([]int, max+1)
    output := make([]int, len(arr))
    
    for _, v := range arr {
        count[v]++
    }
    
    for i := 1; i <= max; i++ {
        count[i] += count[i-1]
    }
    
    for i := len(arr)-1; i >= 0; i-- {
        output[count[arr[i]]-1] = arr[i]
        count[arr[i]]--
    }
    
    return output
}

Поразрядная сортировка (Radix Sort)

• Сортирует по разрядам (единицы, десятки, сотни)
• Сложность O(d*(n + k)), где d - количество разрядов
• Эффективен для сортировки строк или чисел с фиксированным размером

Блочная сортировка (Bucket Sort)

• Разбивает данные на "ведра", каждое из которых сортируется отдельно
• Эффективен при равномерном распределении данных

Практическое применение в Go

В стандартной библиотеке Go используется гибридный подход:

• Для примитивных типов (int, float64, string) - интроспективная сортировка (гибрид QuickSort и HeapSort)
• Для пользовательских типов - адаптивная сортировка слиянием (TimSort)

// Стандартная сортировка в Go
package main

import (
    "fmt"
    "sort"
)

func main() {
    // Сортировка срезов
    nums := []int{5, 2, 6, 3, 1, 4}
    sort.Ints(nums)
    fmt.Println(nums) // [1 2 3 4 5 6]
    
    // Сортировка структур
    people := []struct {
        Name string
        Age  int
    }{
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35},
    }
    
    sort.Slice(people, func(i, j int) bool {
        return people[i].Age < people[j].Age
    })
}

Критерии выбора алгоритма сортировки

При выборе алгоритма в реальных проектах я учитываю:

1. Размер данных: Для маленьких массивов (<50 элементов) Insertion Sort может быть быстрее QuickSort
2. Характер данных: Для почти отсортированных данных адаптивные алгоритмы (Timsort) эффективнее
3. Требования к памяти: In-place сортировки (HeapSort, QuickSort) предпочтительнее при ограниченной памяти
4. Стабильность: Если важно сохранить порядок равных элементов - нужна устойчивая сортировка
5. Тип данных: Для чисел с малым диапазоном Counting Sort может быть оптимальным

В production-коде на Go я обычно полагаюсь на стандартную библиотеку sort, которая тщательно оптимизирована. Однако понимание различных алгоритмов позволяет принимать осознанные решения при необходимости реализации кастомной сортировки или оптимизации критичных по производительности участков кода. Особенно важно это при работе с большими объемами данных в распределенных системах или системах реального времени.