Алгоритм — это конечная последовательность точно определенных шагов, которая по входным данным за конечное число операций дает результат. В Java алгоритм — это обычный метод: он принимает данные (массив, список, строку) и возвращает ответ или меняет структуру на месте.
Содержание
Ниже разберем самые ходовые алгоритмы на Java — линейный и двоичный поиск, сортировку выбором и жадный алгоритм — с рабочим кодом и реальным выводом. Отдельно покажу готовые методы из стандартной библиотеки, которыми эти задачи решают в настоящих проектах, и как читать оценку сложности.
Как измеряют сложность алгоритма
Прежде чем сравнивать алгоритмы, нужен язык оценки скорости. Его дает O-нотация: она описывает, как растет число операций при увеличении объема данных n, отбрасывая константы.
Считают не секунды (они зависят от машины), а порядок роста. O(1) — время не зависит от n, O(log n) — растет очень медленно, O(n) — линейно, O(n log n) — чуть медленнее линейного, O(n^2) — квадратично и болезненно на больших данных.
| Алгоритм | Сложность (в среднем) | Условие |
|---|---|---|
| Линейный поиск | O(n) | массив в любом порядке |
| Двоичный поиск | O(log n) | массив отсортирован |
| Сортировка выбором | O(n^2) | учебная реализация |
Arrays.sort для примитивов |
O(n log n) | двухопорный quicksort |
Arrays.sort для объектов |
O(n log n) | TimSort, устойчивая |
Разница O(n) и O(log n) видна на числах: чтобы найти элемент в миллионе значений, линейный поиск в худшем случае сделает около миллиона сравнений, а двоичный — около 20.
Линейный поиск: простой и медленный
Линейный поиск проходит массив с начала и сравнивает каждый элемент с искомым, пока не найдет совпадение или не дойдет до конца. Он не требует сортировки, но в худшем случае перебирает все n элементов, поэтому его сложность — O(n).
public class LinearSearch {
static int indexOf(int[] a, int target) {
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
return i; // нашли - возвращаем позицию
}
}
return -1; // дошли до конца - элемента нет
}
public static void main(String[] args) {
int[] data = {7, 3, 9, 1, 5, 8};
System.out.println("индекс 5: " + indexOf(data, 5));
System.out.println("индекс 4: " + indexOf(data, 4));
}
}Вывод программы:
индекс 5: 4
индекс 4: -1
Значение 5 стоит на позиции 4 (индексы в Java считаются с нуля), поэтому метод вернул 4. Числа 4 в массиве нет — вернулся признак «не найдено» -1. Линейный поиск берут, когда данных мало или они не отсортированы и сортировать их ради одного поиска невыгодно.
Двоичный поиск: делим пополам
Двоичный поиск работает только по отсортированному массиву. Он смотрит средний элемент и за одно сравнение отбрасывает половину диапазона: если искомое меньше среднего — продолжает слева, если больше — справа. За счет этого сложность падает до O(log n).
Проследим поиск числа 9 в массиве {1, 3, 4, 6, 7, 9, 11, 15} (индексы 0-7):
- Границы 0 и 7, середина — индекс 3, там 6. 9 больше 6 — ищем правее, границы 4 и 7.
- Границы 4 и 7, середина — индекс 5, там 9. Совпадение — ответ 5.
Тот же алгоритм в коде, итеративный вариант:
public class BinarySearch {
static int search(int[] a, int target) {
int low = 0, high = a.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // защита от переполнения
if (a[mid] == target) {
return mid;
} else if (a[mid] < target) {
low = mid + 1; // цель правее середины
} else {
high = mid - 1; // цель левее середины
}
}
return -1;
}
public static void main(String[] args) {
int[] sorted = {1, 3, 4, 6, 7, 9, 11, 15};
System.out.println("индекс 9: " + search(sorted, 9));
System.out.println("индекс 6: " + search(sorted, 6));
System.out.println("индекс 2: " + search(sorted, 2));
}
}Вывод программы:
индекс 9: 5
индекс 6: 3
индекс 2: -1
Середину считают как low + (high - low) / 2, а не (low + high) / 2: на больших границах сумма low + high может выйти за пределы int и стать отрицательной, а первый вариант этого избегает. Важна граница применимости: если массив не отсортирован, двоичный поиск вернет неверный результат, а не ошибку, — сортировку надо гарантировать заранее.
Сортировка выбором
Сортировка выбором на каждом шаге находит минимум в неотсортированной части массива и ставит его в начало этой части. Реализация наглядная, но делает вложенные проходы, поэтому ее сложность — O(n^2).
Проследим сортировку массива {5, 1, 4, 2, 8} по шагам (жирным — минимум, который встает на место):
- Минимум всего массива — 1, меняем с первым:
{1, 5, 4, 2, 8}. - Минимум остатка
{5, 4, 2, 8}— это 2, меняем с 5:{1, 2, 4, 5, 8}. - Минимум остатка
{4, 5, 8}— это 4, уже на месте:{1, 2, 4, 5, 8}. - Остается
{5, 8}, оба на местах — массив отсортирован.
import java.util.Arrays;
public class SelectionSort {
static void sort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j; // запомнили индекс меньшего
}
}
int tmp = a[min]; // обмен a[i] и a[min]
a[min] = a[i];
a[i] = tmp;
}
}
public static void main(String[] args) {
int[] data = {5, 1, 4, 2, 8};
sort(data);
System.out.println(Arrays.toString(data));
}
}Вывод программы:
[1, 2, 4, 5, 8]
Сортировка выбором ценна как учебная: она показывает механику «найти минимум — поставить на место». В рабочем коде свою сортировку писать не нужно — для этого есть библиотечные методы, которые быстрее и уже отлажены.
Готовые алгоритмы в стандартной библиотеке Java
Поиск и сортировку в Java почти всегда решают штатными методами. Класс java.util.Arrays дает sort и binarySearch для массивов, а Collections.sort сортирует списки. Это быстрее самописных O(n^2)-вариантов и не содержит типичных ошибок с границами.
import java.util.Arrays;
public class StdLib {
public static void main(String[] args) {
int[] data = {5, 1, 4, 2, 8, 3};
Arrays.sort(data); // сортировка на месте
System.out.println("отсортировано: " + Arrays.toString(data));
int pos = Arrays.binarySearch(data, 4); // элемент есть
System.out.println("индекс 4: " + pos);
int miss = Arrays.binarySearch(data, 7); // элемента нет
System.out.println("для 7: " + miss);
}
}Вывод программы:
отсортировано: [1, 2, 3, 4, 5, 8]
индекс 4: 3
для 7: -6
Здесь важная деталь Java, которая часто путает новичков: Arrays.binarySearch при отсутствии элемента возвращает не -1, а отрицательное число вида -(точка вставки) - 1. Для 7 точка вставки — индекс 5 (между 5 и 8), поэтому ответ -6. По этому числу можно понять, куда вставить элемент, чтобы массив остался отсортированным. И binarySearch тоже требует заранее отсортированный массив — иначе результат неопределен.
Жадный алгоритм на примере размена монет
Жадный алгоритм на каждом шаге делает локально лучший выбор в надежде, что из таких шагов сложится глобально хорошее решение. Классический пример — размен суммы минимальным числом монет: каждый раз берем самую крупную монету, которая не превышает остаток.
public class GreedyCoins {
static int[] coins = {10, 5, 2, 1}; // номиналы по убыванию
static void change(int amount) {
int rest = amount;
for (int coin : coins) {
int count = rest / coin; // сколько таких монет влезает
if (count > 0) {
System.out.println(coin + " x " + count);
}
rest = rest % coin; // остаток к размену
}
}
public static void main(String[] args) {
change(27);
}
}Вывод программы:
10 x 2
5 x 1
2 x 1
Для 27 при номиналах 10, 5, 2, 1 жадный алгоритм дает 4 монеты, и это оптимум. Но жадность работает не всегда: на номиналах 1, 3, 4 для суммы 6 жадный возьмет 4 + 1 + 1 (три монеты), а оптимум — 3 + 3 (две). Поэтому жадный подход применяют, когда доказано, что локальный выбор ведет к глобальному оптимуму; иначе берут динамическое программирование.
Выводы
- Алгоритм в Java — это метод над данными; сравнивают алгоритмы по O-нотации, то есть по порядку роста числа операций от объема данных.
- Линейный поиск O(n) не требует сортировки; двоичный поиск O(log n) в разы быстрее, но работает только по отсортированному массиву.
- Сортировка выбором O(n^2) — учебная; в реальном коде берут
Arrays.sortиArrays.binarySearch, помня, что при промахеbinarySearchвозвращает-(точка вставки) - 1. - Жадный алгоритм прост и быстр, но дает оптимум не для любых входных данных — границу применимости нужно проверять.
Где применяется и что учить дальше
Поиск и сортировка — фундамент почти любой программы: выборка записей из коллекции, подготовка данных к двоичному поиску, обработка пользовательского ввода. Понимание O-нотации помогает заранее оценить, выдержит ли алгоритм рост данных, а не ловить тормоза уже в проде.
Освойте тему на практике
Чтобы освоить синтаксис Java и уверенно писать такие методы с нуля, посмотрите курс Java Basic в Otus — он рассчитан на старт с азов языка. Оценить формат и уровень до оплаты помогают бесплатные открытые уроки Otus — живые занятия с преподавателями.
Смежные темы: Scala: что нужно знать начинающим программистам, Криптография: что нужно знать про алгоритмы.
FAQ
Нужно ли писать поиск и сортировку вручную в реальных проектах? Обычно нет. Для сортировки берут Arrays.sort или Collections.sort, для поиска в отсортированном массиве — Arrays.binarySearch. Самописные реализации нужны учебно или когда требуется нестандартная логика сравнения.
Почему двоичный поиск не стоит применять к LinkedList? Двоичному поиску нужен быстрый доступ к элементу по индексу за O(1), как в массиве или ArrayList. У LinkedList доступ по индексу — O(n), поэтому выигрыш O(log n) теряется, и линейный проход оказывается не хуже.
Что означает отрицательный результат Arrays.binarySearch? Это не просто «не найдено»: метод возвращает -(точка вставки) - 1. Точка вставки — индекс, куда встал бы элемент, чтобы массив остался отсортированным. По этому числу удобно сразу вставлять элемент в нужную позицию.
