🐹 Go

Algoritmos de ordenação em Go (Golang): um guia detalhado

Lição 29 / 35 • Leitura completa da teoria

Что это такое и зачем? (аналогия из реальной жизни)

Представь, что ты — учитель физкультуры, и у тебя есть класс из 30 учеников. Вам нужно построиться по росту для общей фотографии. Сейчас все стоят вразнобой: высокий Петя стоит рядом с низкой Машей, а средний Коля затерялся где-то в середине. Твоя задача — упорядочить их так, чтобы самый низкий стоял слева, а самый высокий — справа.

Это и есть сортировка — процесс приведения набора элементов в определённый порядок. В программировании мы сортируем не людей, а данные: числа, строки, записи в базе данных. Зачем это нужно? Представь, что ты ищешь телефон в записной книжке. Если контакты не отсортированы по алфавиту, тебе придётся просмотреть все 200 записей. А если они отсортированы — ты открываешь букву «И» и сразу находишь «Иванова».

Вот ещё примеры из жизни, где работает сортировка:

Магазин: товары на полках расставлены по категориям и цене
Библиотека: книги стоят по алфавиту авторов
Музыкальный плеер: треки можно отсортировать по названию, исполнителю или году
Социальная сеть: посты показываются от новых к старым

В программировании сортировка — это фундаментальный алгоритм, который используется повсеместно. Без неё не работали бы поисковые системы, интернет-магазины и даже твой телефон.

Важно: Сортировка — это не просто «расставить по порядку». Это целая наука о том, как это сделать максимально быстро и эффективно. Разные алгоритмы сортировки работают по-разному, и выбор правильного может ускорить программу в тысячи раз.

Теория: как это работает изнутри

Давай заглянем «под капот» алгоритмов сортировки. Представь, что у нас есть массив чисел: [5, 3, 8, 1, 9, 2]. Наша цель — получить [1, 2, 3, 5, 8, 9].

Основные понятия

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

Термин	Что это значит	Пример
Сравнение	Проверка, какой из двух элементов больше	5 > 3 → true
Обмен (своп)	Перестановка двух элементов местами	Было [5,3], стало [3,5]
Проход	Один полный просмотр всего массива	Проверили все пары от начала до конца
Устойчивость	Сохранение порядка одинаковых элементов	Если два «5» — какая была первой, та и останется

Как измерить скорость алгоритма?

Программисты используют специальную нотацию — «О-большое» (Big O notation). Она показывает, как быстро растёт время работы алгоритма при увеличении количества данных.

O(n²) — «квадратичная сложность». Если данных в 2 раза больше, время работы вырастает в 4 раза. Плохо для больших массивов.
O(n log n) — «линейно-логарифмическая сложность». Если данных в 2 раза больше, время работы вырастает чуть больше, чем в 2 раза. Хорошо.
O(n) — «линейная сложность». Время растёт пропорционально количеству данных. Отлично, но так быстро сортируют только в особых случаях.

Три главных алгоритма для новичка

Мы рассмотрим три алгоритма, которые нужно знать каждому программисту:

Сортировка пузырьком (Bubble Sort) — самая простая для понимания, но медленная
Сортировка вставками (Insertion Sort) — работает как с колодой карт
Быстрая сортировка (Quick Sort) — одна из самых быстрых, используется в реальных проектах

Сортировка пузырьком

Представь, что ты стоишь в очереди и хочешь, чтобы высокие люди ушли в конец. Ты смотришь на двух соседей: если левый выше правого — меняешь их местами. Проходишь так всю очередь один раз — самый высокий «всплывает» в конец, как пузырёк в газировке. Повторяешь, пока все не встанут по порядку.

Сортировка вставками

Представь, что ты собираешь колоду карт. Ты берёшь карты по одной и вставляешь каждую в нужное место среди уже отсортированных. Сначала у тебя одна карта (она уже отсортирована). Потом берёшь вторую — если она меньше первой, ставишь слева. Третью — ищешь её место среди первых двух и т.д.

Быстрая сортировка

Этот алгоритм работает по принципу «разделяй и властвуй». Ты выбираешь один элемент — опорный (pivot). Все элементы меньше опорного — налево, все больше — направо. Потом повторяешь то же самое для левой и правой части. И так до тех пор, пока не останутся части из одного элемента — они уже отсортированы.

Важно: Встроенная функция сортировки в Go (sort.Slice) использует быструю сортировку. Но чтобы понять, как она работает, нужно изучить и простые алгоритмы — они развивают алгоритмическое мышление.

Синтаксис в Go (Golang): все формы и варианты

В Go есть несколько способов отсортировать данные. Давай разберём их все — от встроенных функций до ручной реализации.

1. Встроенная сортировка для срезов (слайсов)

Go предоставляет мощный пакет sort. Вот его основные функции:

Функция	Что делает	Пример
`sort.Ints(slice)`	Сортирует срез целых чисел по возрастанию	`sort.Ints(numbers)`
`sort.Float64s(slice)`	Сортирует срез дробных чисел	`sort.Float64s(prices)`
`sort.Strings(slice)`	Сортирует строки в алфавитном порядке	`sort.Strings(names)`
`sort.IntsAreSorted(slice)`	Проверяет, отсортирован ли срез	`sort.IntsAreSorted(nums)` → true/false
`sort.Slice(slice, lessFunc)`	Сортирует срез по произвольному правилу	Сортировка по убыванию или по полю структуры
`sort.SearchInts(slice, x)`	Бинарный поиск в отсортированном срезе	Ищет индекс числа x

2. Сортировка с произвольным правилом (sort.Slice)

Это самая гибкая функция. Ты передаёшь ей срез и функцию, которая определяет, какой элемент должен быть раньше:

// Сортировка чисел по убыванию
numbers := []int{5, 2, 8, 1, 9}
sort.Slice(numbers, func(i, j int) bool {
    return numbers[i] > numbers[j]  // если i-й больше j-го — меняем
})
fmt.Println(numbers) // [9 8 5 2 1]

3. Сортировка структур

Чаще всего нужно сортировать не просто числа, а сложные данные. Например, список студентов:

type Student struct {
    Name  string
    Grade int
}

students := []Student{
    {"Анна", 85},
    {"Борис", 92},
    {"Вика", 78},
}

// Сортируем по оценкам (от высшей к низшей)
sort.Slice(students, func(i, j int) bool {
    return students[i].Grade > students[j].Grade
})

4. Реализация интерфейса sort.Interface

Для продвинутых случаев можно реализовать интерфейс sort.Interface. Он требует три метода: Len(), Less(), Swap():

type ByName []Student

func (s ByName) Len() int           { return len(s) }
func (s ByName) Less(i, j int) bool { return s[i].Name < s[j].Name }
func (s ByName) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

// Использование:
sort.Sort(ByName(students))

Совет: Для 90% задач достаточно sort.Slice. Реализовывать интерфейс нужно только если ты пишешь библиотеку или хочешь переиспользовать логику сортировки.

Примеры кода — от простого к сложному

Теперь давай напишем 7 рабочих примеров. Каждый пример — это полноценная программа, которую можно запустить.

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

package main

import "fmt"

// bubbleSort сортирует срез методом пузырька
func bubbleSort(arr []int) {
    n := len(arr)
    // Внешний цикл: делаем n-1 проходов
    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]
            }
        }
    }
}

func main() {
    numbers := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("До сортировки:", numbers)
    
    bubbleSort(numbers)
    
    fmt.Println("После сортировки:", numbers)
    // Вывод: [11 12 22 25 34 64 90]
}

Объяснение: На каждом проходе самый большой элемент «всплывает» в конец. После первого прохода 90 оказывается на последнем месте. После второго — 64 на предпоследнем. И так далее.

Пример 2: Сортировка вставками (Insertion Sort)

package main

import "fmt"

// insertionSort сортирует срез методом вставок
func insertionSort(arr []int) {
    n := len(arr)
    // Начинаем со второго элемента (индекс 1)
    for i := 1; i < n; i++ {
        key := arr[i]  // Запоминаем текущий элемент
        j := i - 1     // Начинаем сравнивать с предыдущими
        
        // Сдвигаем элементы вправо, пока не найдём место для key
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]  // Сдвигаем элемент вправо
            j--
        }
        arr[j+1] = key  // Вставляем key на найденное место
    }
}

func main() {
    numbers := []int{12, 11, 13, 5, 6}
    fmt.Println("До сортировки:", numbers)
    
    insertionSort(numbers)
    
    fmt.Println("После сортировки:", numbers)
    // Вывод: [5 6 11 12 13]
}

Объяснение: Представь, что левая часть массива уже отсортирована. Мы берём очередной элемент (key) и вставляем его в правильное место среди отсортированных. Все большие элементы сдвигаются вправо.

Пример 3: Быстрая сортировка (Quick Sort)

package main

import "fmt"

// quickSort сортирует срез методом быстрой сортировки
func quickSort(arr []int, low, high int) {
    if low < high {
        // partition делит массив на две части и возвращает индекс опорного элемента
        pi := partition(arr, low, high)
        
        // Рекурсивно сортируем левую и правую части
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    }
}

// partition выбирает опорный элемент и ставит его на правильное место
func partition(arr []int, low, high int) int {
    pivot := arr[high]  // Опорный элемент — последний
    i := low - 1        // Индекс меньшего элемента
    
    for j := low; j < high; j++ {
        // Если текущий элемент меньше или равен опорному
        if arr[j] <= pivot {
            i++  // Увеличиваем индекс меньшего элемента
            arr[i], arr[j] = arr[j], arr[i]  // Меняем местами
        }
    }
    // Ставим опорный элемент на правильное место
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

func main() {
    numbers := []int{10, 7, 8, 9, 1, 5}
    fmt.Println("До сортировки:", numbers)
    
    quickSort(numbers, 0, len(numbers)-1)
    
    fmt.Println("После сортировки:", numbers)
    // Вывод: [1 5 7 8 9 10]
}

Объяснение: Выбираем опорный элемент (обычно последний). Все элементы меньше него — слева, больше — справа. Затем рекурсивно повторяем для левой и правой частей. Это самый быстрый из трёх алгоритмов.

Пример 4: Встроенная сортировка чисел

package main

import (
    "fmt"
    "sort"
)

func main() {
    // Сортировка целых чисел
    numbers := []int{42, 13, 7, 99, 1, 55}
    fmt.Println("До сортировки:", numbers)
    
    sort.Ints(numbers)  // Встроенная функция!
    
    fmt.Println("После сортировки:", numbers)
    // Вывод: [1 7 13 42 55 99]
    
    // Проверка, отсортирован ли массив
    isSorted := sort.IntsAreSorted(numbers)
    fmt.Println("Массив отсортирован?", isSorted)  // true
    
    // Сортировка дробных чисел
    prices := []float64{19.99, 5.49, 100.00, 0.99}
    sort.Float64s(prices)
    fmt.Println("Цены:", prices)  // [0.99 5.49 19.99 100.00]
    
    // Сортировка строк
    names := []string{"Зоя", "Анна", "Борис", "Вика"}
    sort.Strings(names)
    fmt.Println("Имена:", names)  // [Анна Борис Вика Зоя]
}

Объяснение: Это самый простой способ. Go сам выбирает оптимальный алгоритм (обычно быструю сортировку). Используй его в реальных проектах.

Пример 5: Сортировка по убыванию

package main

import (
    "fmt"
    "sort"
)

func main() {
    numbers := []int{42, 13, 7, 99, 1, 55}
    fmt.Println("До сортировки:", numbers)
    
    // Сортируем по убыванию с помощью sort.Slice
    sort.Slice(numbers, func(i, j int) bool {
        return numbers[i] > numbers[j]  // Меняем знак > на <
    })
    
    fmt.Println("По убыванию:", numbers)
    // Вывод: [99 55 42 13 7 1]
    
    // Сортировка строк по длине
    words := []string{"яблоко", "дом", "компьютер", "кот"}
    sort.Slice(words, func(i, j int) bool {
        return len(words[i]) < len(words[j])  // От коротких к длинным
    })
    fmt.Println("По длине:", words)
    // Вывод: [дом кот яблоко компьютер]
}

Объяснение: sort.Slice — твой главный инструмент для нестандартной сортировки. Функция less определяет, должен ли элемент с индексом i стоять раньше элемента с индексом j.

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

package main

import (
    "fmt"
    "sort"
)

// Person — структура, представляющая человека
type Person struct {
    Name string
    Age  int
    City string
}

func main() {
    people := []Person{
        {"Анна", 25, "Москва"},
        {"Борис", 30, "Санкт-Петербург"},
        {"Вика", 25, "Казань"},
        {"Анна", 20, "Москва"},
    }
    
    fmt.Println("До сортировки:")
    for _, p := range people {
        fmt.Printf("  %s, %d лет, %s
", p.Name, p.Age, p.City)
    }
    
    // Сортируем сначала по имени, потом по возрасту, потом по городу
    sort.Slice(people, func(i, j int) bool {
        // Сначала сравниваем по имени
        if people[i].Name != people[j].Name {
            return people[i].Name < people[j].Name
        }
        // Если имена одинаковые — сравниваем по возрасту
        if people[i].Age != people[j].Age {
            return people[i].Age < people[j].Age
        }
        // Если и возраст одинаковый — сравниваем по городу
        return people[i].City < people[j].City
    })
    
    fmt.Println("
После сортировки (имя → возраст → город):")
    for _, p := range people {
        fmt.Printf("  %s, %d лет, %s
", p.Name, p.Age, p.City)
    }
}

Объяснение: Многоуровневая сортировка — частая задача. Сначала сравниваем по первому полю. Если оно одинаковое — переходим ко второму. И так далее. Это как сортировка в Excel по нескольким колонкам.

Пример 7: Бинарный поиск в отсортированном массиве

package main

import (
    "fmt"
    "sort"
)

func main() {
    // Бинарный поиск работает ТОЛЬКО на отсортированных данных!
    numbers := []int{1, 3, 5, 7, 9, 11, 13, 15}
    
    // Ищем число 7
    index := sort.SearchInts(numbers, 7)
    if index < len(numbers) && numbers[index] == 7 {
        fmt.Printf("Число 7 найдено на позиции %d
", index)
    } else {
        fmt.Println("Число 7 не найдено")
    }
    
    // Ищем число 8 (которого нет)
    index = sort.SearchInts(numbers, 8)
    // index = 4 (место, где должно быть число 8)
    fmt.Printf("Число 8 должно быть на позиции %d
", index)
    
    // Общий случай: sort.Search
    target := 11
    index = sort.Search(len(numbers), func(i int) bool {
        return numbers[i] >= target
    })
    if index < len(numbers) && numbers[index] == target {
        fmt.Printf("Число %d найдено на позиции %d
", target, index)
    }
}

Объяснение: Бинарный поиск — это «младший брат» сортировки. Если данные отсортированы, можно найти элемент за O(log n) вместо O(n). Это как открыть книгу по оглавлению, а не читать каждую страницу.

Сравнение с Python: чем похоже и чем отличается

Если ты уже знаешь Python, тебе будет проще. Давай сравним подходы к сортировке в двух языках:

Операция	Python	Go
Сортировка списка чисел	`sorted(numbers)` или `numbers.sort()`	`sort.Ints(numbers)`
Сортировка по убыванию	`sorted(numbers, reverse=True)`	`sort.Slice(numbers, func(i, j int) bool { return numbers[i] > numbers[j] })`
Сортировка по ключу	`sorted(people, key=lambda p: p.age)`	`sort.Slice(people, func(i, j int) bool { return people[i].Age < people[j].Age })`
Сортировка строк	`sorted(names)`	`sort.Strings(names)`
Проверка на отсортированность	`all(numbers[i] <= numbers[i+1] for i in range(len(numbers)-1))`	`sort.IntsAreSorted(numbers)`
Бинарный поиск	`bisect.bisect_left(numbers, x)`	`sort.SearchInts(numbers, x)`

Главные отличия

Лаконичность: Python короче. sorted(numbers) против sort.Ints(numbers). Но Go выигрывает в производительности.
Типизация: В Go нужно указывать тип данных (sort.Ints для int, sort.Float64s для float). В Python одна функция работает со всем.
Производительность: Go быстрее. Встроенная сортировка Go работает примерно в 2-5 раз быстрее, чем sorted() в Python.
Гибкость: В Python key — это просто функция. В Go нужно писать целую анонимную функцию. Но это даёт больше контроля.
Стабильность: В Python sorted() стабилен (сохраняет порядок равных элементов). В Go sort.Slice нестабилен — порядок равных элементов может измениться.

Совет: Если ты переходишь с Python на Go, запомни: в Go нет «магии». Всё нужно писать явно. Но это делает код более предсказуемым и быстрым.

Типичные ошибки и подводные камни

Даже опытные программисты иногда ошибаются при сортировке. Вот самые частые проблемы:

Ошибка 1: Забыть импортировать пакет sort

// ❌ Ошибка: sort не импортирован
func main() {
    numbers := []int{3, 1, 2}
    sort.Ints(numbers)  // Ошибка компиляции: undefined: sort
}

// ✅ Правильно:
import "sort"

func main() {
    numbers := []int{3, 1, 2}
    sort.Ints(numbers)  // Работает
}

Ошибка 2: Сортировка nil-среза

// ❌ Ошибка: паника при сортировке nil-среза
var numbers []int  // nil-срез
sort.Ints(numbers)  // Паника: runtime error

// ✅ Правильно: проверяем на nil
if numbers != nil {
    sort.Ints(numbers)
}

// Или инициализируем пустым срезом
numbers := []int{}  // Пустой, но не nil
sort.Ints(numbers)  // Работает, ничего не делает

Ошибка 3: Неправильная функция less в sort.Slice

// ❌ Ошибка: неправильное условие
sort.Slice(numbers, func(i, j int) bool {
    return numbers[i] >= numbers[j]  // Должно быть >, не >=
})

// ✅ Правильно:
sort.Slice(numbers, func(i, j int) bool {
    return numbers[i] > numbers[j]  // Строгое неравенство
})

Важно: Функция less должна возвращать true, если элемент i должен стоять перед элементом j. Используй строгое неравенство (< или >), не <= или >=.

Ошибка 4: Сортировка среза, который используется в других горутинах

// ❌ Ошибка: гонка данных (data race)
numbers := []int{3, 1, 2}
go func() {
    sort.Ints(numbers)  // Сортировка в одной горутине
}()
go func() {
    fmt.Println(numbers[0])  // Чтение в другой горутине
}()

// ✅ Правильно: используем мьютекс или копию
numbersCopy := make([]int, len(numbers))
copy(numbersCopy, numbers)
go func() {
    sort.Ints(numbersCopy)  // Сортируем копию
}()

Ошибка 5: Предположение, что sort.Slice стабилен

// ❌ Ошибка: порядок равных элементов может измениться
type Task struct {
    Priority int
    ID       int
}
tasks := []Task{{1, 101}, {2, 102}, {1, 103}}
sort.Slice(tasks, func(i, j int) bool {
    return tasks[i].Priority < tasks[j].Priority
})
// Порядок задач с Priority=1 (101 и 103) может быть любым!

// ✅ Правильно: используем sort.SliceStable для стабильной сортировки
sort.SliceStable(tasks, func(i, j int) bool {
    return tasks[i].Priority < tasks[j].Priority
})
// Теперь 101 гарантированно будет перед 103

Лучшие практики и советы профессионалов

Вот что советуют опытные Go-разработчики:

1. Используй встроенную сортировку, когда можно

Не пиши свою сортировку для реальных проектов. sort.Ints и sort.Slice оптимизированы профессионалами. Твоя реализация пузырька будет в 100 раз медленнее.

2. Для больших данных — sort.Slice

Если у тебя больше 1000 элементов, используй sort.Slice. Он использует быструю сортировку и работает за O(n log n).

3. Для маленьких данных — сортировка вставками

Если у тебя меньше 20 элементов, сортировка вставками может быть быстрее встроенной. Но обычно разница незаметна.

4. Сортируй один раз

Если тебе нужны данные в отсортированном виде несколько раз, отсортируй их один раз и сохрани. Не сортируй каждый раз заново.

5. Используй sort.Search для поиска

После сортировки используй бинарный поиск (sort.Search), а не линейный. Это в разы быстрее.

6. Избегай сортировки в циклах

// ❌ Плохо: сортировка на каждой итерации
for i := 0; i < 100; i++ {
    sort.Ints(data)  // Сортируем 100 раз!
    // ... работаем с data
}

// ✅ Хорошо: сортируем один раз
sort.Ints(data)
for i := 0; i < 100; i++ {
    // ... работаем с уже отсортированными data
}

7. Используй sort.SliceStable для предсказуемости

Если порядок равных элементов важен (например, сортировка задач по приоритету, где задачи с одинаковым приоритетом должны сохранять порядок добавления), используй sort.SliceStable.

8. Тестируй сортировку на граничных случаях

Всегда проверяй:

Пустой срез: []int{}
Срез из одного элемента: []int{42}
Уже отсортированный срез
Срез, отсортированный в обратном порядке
Срез с одинаковыми элементами

Вопросы для самопроверки

Проверь, как ты усвоил материал. Ответ

← Anterior Expressões regulares em Go (Golang): um guia detal Próximo → Algoritmos de busca em Go (Golang): um guia detalh