Сортировка и бинарный поиск
Сортировка и бинарный поиск
В Go не нужно писать сортировку с нуля. Но нужно понимать, когда какой подход работает, чем Slice отличается от SliceStable, и почему один и тот же массив сортируется за разное время на разных версиях Go.
sort.Slice - быстрая сортировка
nums := []int{5, 3, 1, 4, 2}
sort.Slice(nums, func(i, j int) bool {
return nums[i] < nums[j]
})
// [1, 2, 3, 4, 5]
// Сортировка структур
type User struct {
Name string
Age int
}
users := []User{
{"Bob", 30}, {"Alice", 25}, {"Carol", 35},
}
sort.Slice(users, func(i, j int) bool {
return users[i].Age < users[j].Age
})
sort.Slice использует reflection один раз для получения swap-функции, поэтому немного медленнее sort.Sort с sort.Interface. На горячем пути это может быть заметно.
<?php
declare(strict_types=1);
$nums = [5, 3, 1, 4, 2];
sort($nums); // [1, 2, 3, 4, 5] - in-place, переиндексирует
// Сортировка структур через usort + spaceship operator <=>
final readonly class User
{
public function __construct(public string $name, public int $age) {}
}
$users = [
new User('Bob', 30),
new User('Alice', 25),
new User('Carol', 35),
];
usort($users, static fn (User $a, User $b): int => $a->age <=> $b->age);
// [Alice 25, Bob 30, Carol 35]
В PHP - sort() (числа/строки in-place), usort() (с компаратором), asort() (сохраняя ключи), ksort() (по ключам).
from dataclasses import dataclass
nums = [5, 3, 1, 4, 2]
nums.sort() # in-place; sorted(nums) вернёт новый список
# [1, 2, 3, 4, 5]
# Сортировка структур - через key-функцию, а не компаратор
@dataclass(slots=True)
class User:
name: str
age: int
users = [
User("Bob", 30), User("Alice", 25), User("Carol", 35),
]
users.sort(key=lambda u: u.age)
# [Alice 25, Bob 30, Carol 35]
list.sort() и sorted() принимают key, а не компаратор: key вычисляется один раз на элемент (n вызовов), компаратор - на каждое сравнение (n log n). Компаратор в стиле usort подключается через functools.cmp_to_key, но нужен редко.
Оператор
<=>(spaceship) возвращает -1/0/1 - именно то, что ждётusort. Это аналогcmp.Compareиз Go 1.21.
sort.Interface - для повторного использования
type ByName []User
func (a ByName) Len() int { return len(a) }
func (a ByName) Less(i, j int) bool { return a[i].Name < a[j].Name }
func (a ByName) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
sort.Sort(ByName(users))
Когда один и тот же тип сортируется в разных местах - выноси sort.Interface в reusable тип.
<?php
declare(strict_types=1);
final class UserComparator
{
public static function byName(User $a, User $b): int
{
return $a->name <=> $b->name;
}
public static function byAge(User $a, User $b): int
{
return $a->age <=> $b->age;
}
/** Multi-key: сначала по возрасту, потом по имени */
public static function byAgeThenName(User $a, User $b): int
{
return $a->age <=> $b->age
?: $a->name <=> $b->name;
}
}
usort($users, UserComparator::byName(...)); // PHP 8.1+ first-class callable syntax
В PHP компараторы вытаскивают в final class со статическими методами или в invokable-объекты - удобно тестировать.
from operator import attrgetter
# Переиспользуемые key-функции вместо sort.Interface:
# attrgetter быстрее lambda и читается как декларация
by_name = attrgetter("name")
by_age = attrgetter("age")
# Multi-key: сначала по возрасту, потом по имени
by_age_then_name = attrgetter("age", "name")
users.sort(key=by_name)
Когда один и тот же тип сортируется в разных местах - выноси key-функции в константы модуля рядом с классом. Тестировать их проще, чем компараторы: одна функция - одно значение.
UserComparator::byName(...)- PHP 8.1+ синтаксис «first-class callable». До этого писали[UserComparator::class, 'byName']или замыкание.
Бинарный поиск
// Через sort.Search (возвращает индекс первого элемента, где f(i) == true)
nums := []int{1, 3, 5, 7, 9, 11}
target := 7
idx := sort.Search(len(nums), func(i int) bool {
return nums[i] >= target
})
if idx < len(nums) && nums[idx] == target {
fmt.Printf("Найден на позиции %d\n", idx)
}
// С Go 1.21: slices.BinarySearch
import "slices"
idx, found := slices.BinarySearch(nums, target)
slices.BinarySearch короче и не требует замыкания. Работает только с упорядоченными типами (cmp.Ordered).
<?php
declare(strict_types=1);
/**
* Бинарный поиск на отсортированном массиве.
* @return int Индекс или -1, если не найдено.
*/
function binarySearch(array $nums, int $target): int
{
$lo = 0;
$hi = count($nums) - 1;
while ($lo <= $hi) {
$mid = intdiv($lo + $hi, 2);
if ($nums[$mid] === $target) {
return $mid;
}
if ($nums[$mid] < $target) {
$lo = $mid + 1;
} else {
$hi = $mid - 1;
}
}
return -1;
}
$nums = [1, 3, 5, 7, 9, 11];
$idx = binarySearch($nums, 7); // 3
В PHP native бинарного поиска нет - array_search() это O(n) линейный обход. Если данные отсортированы и поиск горячий - реализуй вручную.
from bisect import bisect_left
# Через bisect_left (возвращает индекс первого элемента >= target) -
# прямой аналог sort.Search
nums = [1, 3, 5, 7, 9, 11]
target = 7
idx = bisect_left(nums, target)
if idx < len(nums) and nums[idx] == target:
print(f"Найден на позиции {idx}")
# Аналога slices.BinarySearch с флагом found в stdlib нет - обёртка в три строки
def binary_search(nums: list[int], target: int) -> tuple[int, bool]:
idx = bisect_left(nums, target)
return idx, idx < len(nums) and nums[idx] == target
idx, found = binary_search(nums, target)
Модуль bisect - это только поиск позиции; bisect_left и bisect_right отличаются тем, куда встанет дубликат. bisect.insort вставляет с сохранением порядка, но сама вставка в список O(n).
array_search($needle, $arr)всегда O(n), не используй его как замену бинарного поиска. Для частых поисков на отсортированном наборе - либо ручная реализация, либо переход на hash-структуру (isset($index[$key]), O(1)).
Как устроены сортировки из таблицы
Сначала коротко - что делают алгоритмы, которые встретятся в таблице ниже.
- Bubble sort (пузырёк) и insertion sort (вставками) - простые O(n²): пузырёк много раз проходит массив и меняет местами соседей, стоящих не по порядку; вставками берёт элементы по одному и вдвигает каждый на своё место в уже отсортированное начало.
- Quicksort выбирает опорный элемент (pivot), раскладывает массив на «меньше опорного» и «больше опорного» (partition) и рекурсивно сортирует обе части. На удачных опорных части примерно равны, и выходит O(n log n); если опорный раз за разом оказывается минимумом или максимумом, части вырождаются в «ничего» и «всё остальное» - это худший случай O(n²).
Merge sort и откуда берётся n log n
Merge sort (сортировка слиянием) делает наоборот: сначала делит, потом наводит порядок.
- Делим массив пополам, каждую половину сортируем тем же способом (рекурсивно), пока не останутся куски из одного элемента - они уже отсортированы.
- Сливаем две отсортированные половины в одну. Слияние идёт двумя указателями: по одному на начало каждой половины. Сравниваем два элемента под указателями, меньший кладём в результат и двигаем его указатель. Когда одна половина кончилась, хвост другой дописываем целиком. Каждый элемент перекладывается один раз, поэтому слияние кусков общей длиной n стоит O(n).
слить [1 4 7] и [2 3 9]:
1<2 → 1 4>2 → 2 4>3 → 3 4<9 → 4 7<9 → 7 хвост → 9
итог: [1 2 3 4 7 9]
Откуда n log n: деление пополам даёт log₂ n уровней, а на каждом уровне все слияния вместе перекладывают ровно n элементов. Итого n на каждом из log₂ n уровней - O(n log n), причём в любом случае, не только в среднем. Цена - буфер под результат слияния, O(n) дополнительной памяти. При равных элементах слияние берёт элемент из левой половины первым, поэтому merge sort стабилен (что это значит - в разделе о стабильной сортировке).
Сравнение алгоритмов
| Алгоритм | Среднее | Худшее | Память | Стабильный |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | Да |
| Insertion Sort | O(n²) | O(n²) | O(1) | Да |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Да |
| Quick Sort | O(n log n) | O(n²) | O(log n) | Нет |
| sort.Slice (Go) | O(n log n) | O(n log n) | O(log n) | Нет |
С Go 1.19 sort.Slice использует pdqsort (pattern-defeating quicksort) - гибрид рекурсивных quicksort и heapsort:
- быстрый quicksort на типичных данных;
- переключается в heapsort при подозрении на adversarial input → гарантирует O(n log n) в худшем случае;
- использует insertion sort на маленьких подмассивах (до 12 элементов), где он быстрее из-за cache locality;
- детектирует уже отсортированные/обратно отсортированные участки и обрабатывает их за O(n).
На реальных данных это даёт 2-3× ускорение против старого sort.Sort (introsort).
С PHP 8.0
sort/usortстабильны: внутренний гибрид quicksort и insertion sort (zend_sort) остался прежним, но при равенстве элементов теперь учитывается их исходный порядок. Отдельного стабильного варианта больше не нужно. Особого ускорения на уже отсортированных данных, как у Timsort в Python, нет: сложность остаётся O(n log n).
Грубые ориентиры по скорости
На современном x86 ядре slices.Sort для []int:
| Размер | Время |
|---|---|
| 1 000 | ~30 мкс |
| 100 000 | ~5 мс |
| 1 000 000 | ~60 мс |
Цифры зависят от распределения данных, типа элементов и компаратора. Всегда замеряй через go test -bench на своём профиле - не доверяй ориентирам.
Стабильная сортировка
Стабильная сортировка сохраняет относительный порядок равных элементов. Важно при multi-key sort: сначала сортируешь по фамилии, потом по департаменту - фамилии внутри департамента остаются упорядоченными только при стабильной сортировке.
// sort.Slice - НЕ стабильная (равные элементы могут поменять порядок)
// sort.SliceStable - стабильная, но заметно медленнее: in-place слияние
// без буфера, O(n log² n) перестановок, на больших слайсах в разы
sort.SliceStable(users, func(i, j int) bool {
return users[i].Age < users[j].Age
})
Не платишь за стабильность, когда она не нужна - Slice быстрее.
В PHP 8.0+
usortстабилен по умолчанию (тот жеzend_sort, но с учётом исходного порядка при равенстве) - отдельного «stable»-варианта не нужно. На PHP 7.x для стабильной сортировки добавляли индекс в компаратор как tiebreaker. Если код должен работать на legacy-версиях - см. ниже.
<?php
declare(strict_types=1);
// PHP 8.0+ - просто usort, оно уже stable
usort($users, static fn (User $a, User $b): int => $a->age <=> $b->age);
// Legacy-trick для PHP < 8.0: добавить индекс как tiebreaker
$indexed = array_map(
static fn (int $i, User $u): array => ['idx' => $i, 'user' => $u],
array_keys($users),
$users,
);
usort($indexed, static fn (array $a, array $b): int =>
$a['user']->age <=> $b['user']->age
?: $a['idx'] <=> $b['idx']
);
$users = array_column($indexed, 'user');
# list.sort и sorted - ВСЕГДА стабильные (Timsort), отдельного варианта нет
users.sort(key=lambda u: u.age)
# Поэтому multi-key sort делают двумя проходами: сначала вторичный ключ,
# потом первичный - стабильность сохранит порядок внутри групп
users.sort(key=lambda u: u.name)
users.sort(key=lambda u: u.age)
Нет и «нестабильного, но быстрого» режима - Timsort и так работает за O(n) на уже упорядоченных участках, так что платить за стабильность не приходится.
Counting / Radix sort: когда обходят O(n log n)
Граница O(n log n) фундаментальна только для сортировок сравнением. Если знаешь диапазон значений - есть линейные алгоритмы.
Counting sort
Для целых в небольшом диапазоне (например, возраст 0-150):
func countingSort(nums []int, maxVal int) []int {
count := make([]int, maxVal+1)
for _, v := range nums {
count[v]++
}
out := make([]int, 0, len(nums))
for v, c := range count {
for ; c > 0; c-- {
out = append(out, v)
}
}
return out
}
<?php
declare(strict_types=1);
/**
* @param array<int> $nums
* @return array<int>
*/
function countingSort(array $nums, int $maxVal): array
{
$count = array_fill(0, $maxVal + 1, 0);
foreach ($nums as $v) {
$count[$v]++;
}
$out = [];
foreach ($count as $value => $cnt) {
for ($i = 0; $i < $cnt; $i++) {
$out[] = $value;
}
}
return $out;
}
def counting_sort(nums: list[int], max_val: int) -> list[int]:
count = [0] * (max_val + 1)
for v in nums:
count[v] += 1
out: list[int] = []
for v, c in enumerate(count):
out.extend([v] * c) # c копий значения v одним вызовом
return out
Время - O(n + k), где k - диапазон значений. На сортировке миллиона возрастов работает в разы быстрее quicksort.
Radix sort
Разбивает ключ на разряды и применяет counting sort по каждому. Используется в специализированных библиотеках (например, golang.org/x/exp/slices экспериментирует с radix). В стандартной библиотеке нет - слишком ситуативно.
Пакет slices (Go 1.21+)
import "slices"
nums := []int{3, 1, 4, 1, 5}
slices.Sort(nums) // сортировка
slices.SortStableFunc(nums, cmp.Compare) // стабильная с компаратором
slices.SortFunc(nums, cmp.Compare) // нестабильная с компаратором
slices.Contains(nums, 4) // O(n) поиск
slices.Index(nums, 4) // индекс или -1
slices.Min(nums) // минимум
slices.Max(nums) // максимум
slices.BinarySearch(nums, 4) // O(log n) на отсортированном
Новый API быстрее старого sort за счёт generics - нет reflection. Используй slices в новом коде, sort - только для совместимости с sort.Interface библиотек.
В PHP набор аналогичных функций давно встроен в ядро:
<?php
declare(strict_types=1);
$nums = [3, 1, 4, 1, 5];
sort($nums); // [1, 1, 3, 4, 5] - in-place
$copy = $nums; sort($copy); // сортировка копии
usort($nums, fn($a, $b) => $a <=> $b); // с компаратором (stable с PHP 8.0)
in_array(4, $nums, strict: true); // O(n) поиск
$idx = array_search(4, $nums, strict: true); // O(n), индекс или false
min($nums); // минимум
max($nums); // максимум
// asort/ksort/uasort/uksort - вариации с сохранением ключей
asort($users); // сортирует значения, сохраняет ключи
ksort($users); // сортирует по ключам
Аналоги разбросаны по встроенным функциям и модулю bisect:
from bisect import bisect_left
nums = [3, 1, 4, 1, 5]
nums.sort() # сортировка in-place
sorted(nums, key=lambda v: v) # копия, стабильная, с key-функцией
# нестабильного варианта нет: Timsort всегда стабилен
4 in nums # O(n) поиск
nums.index(4) # индекс или ValueError (не -1)
min(nums) # минимум
max(nums) # максимум
bisect_left(nums, 4) # O(log n) на отсортированном
В PHP массивы имеют семантику значения (копия при присваивании, реализованная через copy-on-write), а сортировка написана на C и reflection не использует. На крупных датасетах разница с Go измеримая, но для типичных HTTP-запросов это не bottleneck.
Когда какой выбор
| Сценарий | API |
|---|---|
[]int, []string в новом коде | slices.Sort |
| Структура, простой компаратор | slices.SortFunc |
| Нужна стабильность | slices.SortStableFunc |
| Один и тот же тип в 5+ местах | sort.Sort с sort.Interface |
| Числа в малом диапазоне, миллион элементов | counting sort вручную |
| Найти k-й элемент без полной сортировки | container/heap или quickselect |
| Поиск в отсортированном | slices.BinarySearch |
Типичные ошибки
1. Неправильное направление Less
// БАГ: возвращает по убыванию, хотя задумано по возрастанию
sort.Slice(nums, func(i, j int) bool {
return nums[i] > nums[j] // > вместо <
})
<?php
declare(strict_types=1);
// PHP-аналог: путаница в знаке spaceship-оператора
// БАГ: $b - $a сортирует по убыванию вместо возрастания
usort($nums, static fn (int $a, int $b): int => $b <=> $a); // DESC, не ASC
// Правильно - $a <=> $b для возрастания:
usort($nums, static fn (int $a, int $b): int => $a <=> $b);
from functools import cmp_to_key
# БАГ: перепутаны a и b в компараторе - сортирует по убыванию
nums.sort(key=cmp_to_key(lambda a, b: b - a)) # DESC, не ASC
# Или забытый reverse=True, оставшийся от соседнего отчёта
nums.sort(reverse=True)
# Правильно - просто nums.sort(): с key-функцией знак перепутать негде
nums.sort()
Less должен вернуть true, когда элемент i должен идти раньше j.
2. Сортировка float с NaN
nums := []float64{1.0, math.NaN(), 2.0}
sort.Float64s(nums) // NaN портит порядок
<?php
declare(strict_types=1);
// PHP - то же поведение: NAN не сравнивается ни с чем.
$nums = [1.0, NAN, 2.0];
sort($nums); // порядок NAN не определён, нарушает сортировку
// Фильтрация NAN до сортировки:
$nums = array_values(array_filter($nums, static fn (float $v): bool => !is_nan($v)));
sort($nums);
// Или кастомный компаратор - NAN в конец:
usort($nums, static function (float $a, float $b): int {
if (is_nan($a)) return 1;
if (is_nan($b)) return -1;
return $a <=> $b;
});
import math
# То же поведение: nan не сравнивается ни с чем, sort молча портит порядок
nums = [1.0, math.nan, 2.0]
nums.sort() # NaN портит порядок
# Фильтрация NaN до сортировки:
nums = [v for v in nums if not math.isnan(v)]
nums.sort()
# Или key-функция - NaN в конец: кортежи сравниваются поэлементно,
# False < True, поэтому все nan уходят в хвост
nums.sort(key=lambda v: (math.isnan(v), v))
NaN не сравнивается ни с чем (NaN < x всегда false). Фильтруй NaN до сортировки или используй кастомный компаратор с math.IsNaN.
3. Бинарный поиск в неотсортированном слайсе
idx, found := slices.BinarySearch([]int{3, 1, 4, 1, 5}, 1)
// found == false, хотя 1 есть в слайсе дважды
<?php
declare(strict_types=1);
// PHP-эквивалент: ручной binarySearch без проверки сортировки в рантайме
$nums = [3, 1, 4, 1, 5]; // НЕ отсортирован
$idx = binarySearch($nums, 1); // -1, хотя 1 есть в массиве дважды
// Защитный паттерн: проверка в dev-окружении
// (assert отключается в production через zend.assertions=-1)
$sorted = $nums;
sort($sorted);
assert($nums === $sorted, 'binarySearch requires sorted input');
// Или forsorted-обёртка, гарантирующая контракт:
final class SortedIntArray
{
public function __construct(private readonly array $items)
{
$copy = $items;
sort($copy);
if ($items !== $copy) {
throw new InvalidArgumentException('Input must be sorted');
}
}
}
from bisect import bisect_left
nums = [3, 1, 4, 1, 5] # НЕ отсортирован
idx = bisect_left(nums, 1)
found = idx < len(nums) and nums[idx] == 1
# found == False, хотя единица есть в списке дважды
# Защитный паттерн - обёртка, проверяющая контракт при создании:
class SortedInts:
def __init__(self, items: list[int]) -> None:
if items != sorted(items):
raise ValueError("input must be sorted")
self._items = items
def search(self, target: int) -> tuple[int, bool]:
idx = bisect_left(self._items, target)
return idx, idx < len(self._items) and self._items[idx] == target
BinarySearch ожидает отсортированный вход - это контракт API, не проверяется в рантайме.