Быстрая сортировка (quick sort) — один из самых эффективных алгоритмов сортировки, который используется во многих языках программирования, включая стандартную библиотеку Go.
Её главная идея проста: выбрать опорный элемент, разбить слайс на три части (меньшие, равные и большие), а затем рекурсивно отсортировать каждую часть. Этот принцип называется «разделяй и властвуй» (divide and conquer).
В этой статье рассмотрим реализацию быстрой сортировки на языке Go, разберём каждый шаг и покажем, как она работает на примере — небольшом неотсортированном слайсе.
Суть алгоритма
Быстрая сортировка работает в 3 этапа:
- Выбор опорного элемента (pivot) — обычно берётся средний элемент слайса, но опять-таки этот момент поддаётся оптимизации.
- Разбиение (partition) — все элементы, меньшие опорного, идут в левую часть, равные — в среднюю, большие — в правую.
- Рекурсия — левая и правая части сортируются тем же способом.
Благодаря такому подходу в среднем случае алгоритм работает за время O(n log n).
Реализация на Go
package main
import "fmt"
func quickSort(slice []int) []int {
// Базовый случай: слайс из 0 или 1 элемента уже отсортирован
if len(slice) < 2 {
return slice
}
// Берём опорный элемент (средний по позиции)
pivot := slice[len(slice)/2]
// Создаём три слайса для группировки
var less, equal, greater []int
// Проходим по всем элементам
for _, value := range slice {
switch {
case value < pivot:
less = append(less, value) // меньше опорного
case value == pivot:
equal = append(equal, value) // равны опорному
case value > pivot:
greater = append(greater, value) // больше опорного
}
}
// Рекурсивно сортируем левую и правую части
result := append(quickSort(less), equal...)
result = append(result, quickSort(greater)...)
return result
}
func main() {
slice := []int{64, 25, 12, 22, 11}
sorted := quickSort(slice)
fmt.Println(sorted) // [11 12 22 25 64]
}
Пошаговое объяснение
1. Базовый случай
if len(slice) < 2 {
return slice
}
Если в слайсе 0 или 1 элемент — он уже отсортирован. В таких ситуациях сортировать нечего, поэтому возвращаем слайс как есть.
2. Выбор опорного элемента
pivot := slice[len(slice)/2]
Берём элемент из середины слайса. Почему не первый и не последний?
Представьте уже отсортированный слайс: [1 2 3 4 5]. Если взять первый элемент [1], все остальные элементы попадут в правую часть, а левая будет пустой. Рекурсивный вызов получит слайс [2 3 4 5]. На следующем шаге снова возьмём первый элемент [2] — и так далее. Алгоритм получится O(n²).
Если же взять элемент из середины [3], левая часть будет [1 2], правая — [4 5]. Разделение сбалансированное, и мы получим O(n log n).
Выбор среднего элемента не гарантирует идеального разделения во всех случаях, но защищает от худшего сценария на отсортированных данных.
3. Разбиение на три группы
for _, value := range slice {
switch {
case value < pivot:
less = append(less, value)
case value == pivot:
equal = append(equal, value)
case value > pivot:
greater = append(greater, value)
}
}
Проходим по всем элементам и распределяем их по 3 слайсам:
less— элементы, которые должны стоять до опорного.equal— элементы, равные опорному.greater— элементы, которые должны стоять после опорного.
Почему три группы, а не две? Если в слайсе есть повторяющиеся значения, они попадают в equal. Это ускоряет сортировку: равные элементы не нужно сортировать заново.
4. Рекурсивная сортировка и сборка
result := append(quickSort(less), equal...) result = append(result, quickSort(greater)...)
Рекурсивно сортируем левую и правую части, а затем собираем всё в один слайс:
- Сначала идут отсортированные меньшие элементы.
- Затем все равные опорному.
- Затем отсортированные большие элементы.
Трассировка на примере
Возьмём slice := []int{64, 25, 12, 22, 11}
Первый вызов quickSort([64, 25, 12, 22, 11]).
- Длина = 5 → идём дальше
- Опорный элемент: pivot = slice[2] = 12 (средний по индексу).
- Разбиение:
| Элемент | Сравнение с 12 | Попадает в |
| 64 | 64 > 12 | greater |
| 25 | 25 > 12 | greater |
| 12 | 12 == 12 | equal |
| 22 | 22 > 12 | greater |
| 11 | 11 < 12 | less |
Результат разбиения:
less = [11]equal = [12]greater = [64, 25, 22]
Рекурсивный вызов quickSort([11])
Длина = 1 → возвращаем [11]
Рекурсивный вызов quickSort([64, 25, 22])
- Длина = 3 → идем дальше
- Опорный элемент:
pivot = slice[1] = 25 - Разбиение:
| Элемент | Сравнение с 25 | Попадает в |
| 64 | 64 > 25 | greater |
| 25 | 25 == 25 | equal |
| 22 | 22 < 25 | less |
Результат разбиения:
less = [22]equal = [25]greater = [64]
Рекурсивные вызовы:
quickSort([22])→[22]quickSort([64])→[64]
Сборка: [22] + [25] + [64] = [22, 25, 64]
Финальная сборка
[11] + [12] + [22, 25, 64] = [11, 12, 22, 25, 64]
Готово!
Отличия от других реализаций
Классическая реализация быстрой сортировки делает разбиение на месте (in-place), без выделения новых слайсов. Это экономит память, но сложнее для понимания.
Версия из статьи создаёт новые слайсы less, equal, greater на каждом уровне рекурсии.
Плюсы:
- Код очень понятный и читаемый
- Легко проследить логику
- Отлично подходит для обучения
Минусы:
- Требует больше памяти (O(n log n) вместо O(log n))
- Медленнее из-за аллокаций
Совет: для продакшен-кода лучше использовать встроенную sort.Slice. А эта реализация — для понимания принципа работы.
Сложность алгоритма
| Случай | Время | Память (в нашей реализации) |
| Лучший | O(n log n) | O(n log n) |
| Средний | O(n log n) | O(n log n) |
| Худший | O(n²) | O(n²) |
Худший случай возникает, когда опорный элемент каждый раз оказывается минимальным или максимальным. В нашей реализации опорный элемент берётся из середины, что делает худший случай маловероятным на практике.
Как улучшить реализацию
1. Оптимизация выбора опорного элемента
Вместо простого среднего по индексу можно брать медиану из 3-х (первый, средний, последний). Реализация простая: берём 3 значения, находим среднее по величине — это и будет опорный элемент. Это дополнительно защищает от плохих случаев.
2. Использование сортировки вставками для маленьких слайсов
Для слайсов длиной менее 10-20 элементов сортировка вставками работает быстрее:
func quickSortOptimized(slice []int) []int {
if len(slice) < 10 {
return insertionSort(slice) // сортировка вставками
}
// ... обычная быстрая сортировка
}
3. In-place версия (без аллокаций)
Для серьёзных задач стоит использовать версию, которая сортирует исходный слайс без выделения новых.
Ключевой вывод
Быстрая сортировка — это алгоритм «разделяй и властвуй», который выбирает опорный элемент, разбивает слайс на меньшие, равные и большие элементы, а затем рекурсивно сортирует обе части.
В среднем случае работает за O(n log n), что делает его одним из самых быстрых алгоритмов сортировки на практике.
Приведённая реализация на Go — учебная. Она не самая эффективная (из-за создания новых слайсов), но самая понятная для изучения. Разобравшись в ней, вы легко поймёте и более сложные in-place версии.
А вы приходилось реализовывать быструю сортировку или пользовались встроенными сортировками языка? Делитесь в комментариях!
