Простые сортировки работают за O(N²) и на больших данных безнадёжно медленны. Сортировка слиянием уже даёт O(N·log N), но требует вдвое больше памяти. В этой статье — алгоритмы, которые сортируют так же быстро (или почти), но не транжирят память: сортировка Шелла, быстрая сортировка и совсем необычная поразрядная.

Сортировка Шелла

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

Идея Шелла: сначала наводить грубый порядок дальними прыжками, а точный — потом. Алгоритм сортирует вставками не соседние элементы, а элементы на большом расстоянии h друг от друга (это называют «h-сортировкой»). Такие прыжки быстро подтаскивают далёкие элементы близко к их местам. Затем h уменьшают и повторяют — с всё более мелким шагом, — пока не дойдут до h = 1, то есть до обычной сортировки вставками. Но к этому моменту массив уже почти упорядочен, а на почти упорядоченных данных вставки работают почти за O(N).

Последовательность интервалов h подбирают так, чтобы шаги не повторялись зря; популярный вариант (Кнута) — 1, 4, 13, 40, 121, … (каждый следующий h = 3·h + 1).

void shellSort(long[] a) {
    int n = a.length, h = 1;
    while (h <= n / 3) h = h * 3 + 1;
    while (h > 0) {
        for (int i = h; i < n; i++) {
            long tmp = a[i];
            int j = i;
            while (j >= h && a[j - h] >= tmp) { a[j] = a[j - h]; j -= h; }
            a[j] = tmp;
        }
        h = (h - 1) / 3;
    }
}

Сортировка Шелла хороша для массивов среднего размера (до тысяч элементов), проста в реализации и не требует лишней памяти. По скорости она уступает быстрой сортировке, но её код компактнее и в нём меньше подводных камней.

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

Быстрая сортировка (quicksort) — самый популярный алгоритм сортировки общего назначения. В среднем — O(N·log N), и обычно она обгоняет всех соперников. В основе лежит операция разбиения (partition).

Разбиение выбирает некоторое опорное значение и переставляет массив так, чтобы слева оказались все элементы меньше опорного, а справа — все большие. Сам опорный элемент встаёт ровно на своё окончательное место (граница между группами). Внутри групп порядок пока произвольный.

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

void quickSort(long[] a, int left, int right) {
    if (right <= left) return;
    int pivotIndex = partition(a, left, right);
    quickSort(a, left, pivotIndex - 1);
    quickSort(a, pivotIndex + 1, right);
}

Ахиллесова пята. Скорость зависит от того, насколько удачно опорный элемент делит массив пополам. Если каждый раз он делит примерно поровну — получаем log N уровней и O(N·log N). Но если опорный оказывается наименьшим или наибольшим (так бывает, например, на уже отсортированных данных при наивном выборе), разбиение отсекает всего один элемент, уровней становится N, и алгоритм вырождается в O(N²) — медленнее простых сортировок.

Лекарство — не брать опорным первый попавшийся элемент, а выбирать с умом. Распространённый приём — медиана трёх: взять первый, средний и последний элементы и выбрать опорным средний из них по величине. Это почти исключает вырожденные случаи и заодно упрощает код разбиения. Для совсем маленьких подмассивов часто переключаются на сортировку вставками — на десятке элементов она быстрее из-за меньших накладных расходов.

Поразрядная сортировка

Все алгоритмы выше сравнивают элементы между собой. Поразрядная сортировка (radix sort) — принципиально другой подход: она вообще не сравнивает элементы, а раскладывает их по разрядам.

Работает она так (для чисел): смотрим на последнюю цифру каждого числа и раскладываем числа по десяти «корзинам» (0–9) в порядке следования. Собираем корзины по порядку обратно в массив. Повторяем для следующей цифры (десятков), потом сотен — и так до самого старшего разряда. После прохода по всем разрядам массив оказывается отсортированным. Работает это благодаря тому, что раскладка устойчива — числа с одинаковой цифрой сохраняют относительный порядок, наведённый предыдущими разрядами.

Поразрядная сортировка удивительна тем, что её время — O(N), без всяких логарифмов: она обходится линейным числом проходов. Но у неё есть цена: она применима не к любым данным, а лишь к тем, что раскладываются на разряды (целые числа, строки фиксированной длины), и требует дополнительной памяти под корзины. Поэтому это не универсальный инструмент, а специализированный — зато на своих данных непобедимый.

Что выбрать

  • Быстрая сортировка — выбор по умолчанию для больших массивов общего вида (с защитой опорного элемента вроде «медианы трёх»).
  • Сортировка Шелла — когда важна простота кода, а данные среднего размера; хороший компромисс без лишней памяти.
  • Сортировка слиянием — когда нужна гарантированная O(N·log N) без риска вырождения (и не жалко памяти); особенно для связанных списков и внешних данных.
  • Поразрядная — для больших объёмов целых чисел или коротких строк, где важна скорость O(N).

Коротко

  • Сортировка Шелла — вставки с «дальними прыжками»: сортирует элементы на расстоянии h, постепенно уменьшая h до 1. Проста, без лишней памяти, хороша для средних массивов.
  • Быстрая сортировка — рекурсивное разбиение вокруг опорного элемента; в среднем O(N·log N), самая быстрая на практике. Вырождается в O(N²) при плохом опорном — спасает выбор по «медиане трёх».
  • Поразрядная — без сравнений, раскладка по разрядам; O(N), но только для чисел/строк и с доп. памятью.
  • Порядок роста O(N·log N) — практический потолок сравнительных сортировок; быстрее только специализированные методы вроде поразрядной.

Дальше — двоичные деревья: структура, которая сочетает быстрый поиск упорядоченного массива с быстрой вставкой связанного списка.