Сортировка по двум параметрам java лямбда

Обновлено: 07.01.2025

У меня есть массив объектов person (int age; String name;) .

Как я могу отсортировать этот массив по алфавиту, а затем по возрасту?

какой алгоритм вы бы использовали для этого ?

можно использовать Collections.sort следующим образом:

List<Persons> теперь сортируется по имени, затем по возрасту.

String.compareTo "сравнивает две строки лексикографически" - с docs.

Collections.sort статический метод в собственной библиотеке коллекций. Он выполняет фактическую сортировку, вам просто нужно предоставить компаратор, который определяет, как должны сравниваться два элемента в вашем списке: это достигается путем предоставления вашей собственной реализации compare метод.

для тех, кто может использовать Java 8 streaming API, есть более аккуратный подход, который хорошо документирован здесь: лямбда и сортировка

Я нашел механизм в Java 8 на компаратор:

Итак, вот фрагмент, который демонстрирует алгоритм.

Проверьте ссылку выше для более аккуратного способа и объяснения того, как вывод типа Java делает его немного более неуклюжим для определения по сравнению с LINQ.

вот полный модульный тест для справки:

использование подхода Java 8 Streams.

и подход Java 8 Lambda.

вам нужно реализовать свой собственный Comparator , а затем использовать его, например:

ваш компаратор может выглядеть примерно так:

компаратор сначала сравнивает имена,если они не равны, он возвращает результат от сравнения их, иначе он возвращает результат сравнения при сравнении возрастов обоих лиц.

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

у вашего класса person implement Comparable<Person> а затем реализовать метод compareTo, например:

это будет сортировать сначала по имени (без учета регистра), а затем по возрасту. Затем вы можете запустить Arrays.sort() или Collections.sort() на коллекции или массиве объектов Person.

использовать Comparator а затем поместите объекты в Collection , потом Collections.sort();

гуава это ComparisonChain обеспечивает чистый способ сделать это. Обратитесь к этому ссылке.

утилита для выполнения оператора цепного сравнения. Например:

вы можете сделать так:

или вы можете использовать тот факт, что Collections.sort() (или Arrays.sort() ) стабилен (он не переупорядочивает элементы, которые равны) и использует Comparator сначала сортировать по возрасту, а затем еще один для сортировки по имени.

в этом конкретном случае это не очень хорошая идея, но если вам нужно изменить порядок сортировки во время выполнения, это может быть полезно.

можно использовать универсальный последовательный компаратор для сортировки коллекций по нескольким полям.

создайте столько компараторов, сколько необходимо. После этого вызовите метод "thenComparing" для каждой категории заказа. Это способ делать потоками. См.:

У меня проблемы с пониманием строки с лямбда-выражением в ней.

Как именно он сортирует массив? Откуда берутся а и б?

3 ответа

Сортировать

Метод Java Array.sort принимает массив B как ввод и сортирует его в соответствии с compare(a, b) метод элементов массива. Поэтому, если в массиве хранятся объекты Integer, он будет отсортировать их в соответствии с Integer.compare(a, b) по умолчанию. Это просто сортирует целые числа в порядке возрастания.

Компаратор

В Java есть интерфейс Comparator, который определяет метод, называемый compare(a, b) . Этот метод возвращает ноль if (a==b), отрицательное значение if (a b). В Comparator interface часто используется в методах сортировки или упорядоченных структурах данных, таких как TreeMap.

Лямбда

Теперь, поскольку этот вопрос требует настраиваемого порядка сортировки, вам необходимо указать настраиваемый compare(a, b) метод. К счастью, существует перегруженная версия Array.sort, которая позволяет делать именно это, предоставляя лямбда-метод. Лямбда - это просто встроенная функция. В этом случае он обеспечивает желаемую логику сравнения для сортировки. В вашем примере (a, b) -> являются входными данными лямбда-функции, которые предоставляются методом сортировки. Это стандартный синтаксис лямбда. Сортировка запустит mergesort алгоритм для массива B, используя ваш метод сравнения лямбда, чтобы определить, как упорядочена каждая пара чисел.

Сложная часть

Integer.compare(a%2, b%2) сортирует целые числа a и b по их младшим разрядам. % - оператор модуля (остаток от деления). Если а четное, a%2 возвращает 0. Если нечетное, a%2 возвращает 1. https://leetcode.com/articles/sort-array-by-parity/ неплохо разбирается в логике того, почему эта операция сортирует числа по четности, но это не совсем очевидно. Чем больше проблем вы решите, тем больше ярлыков вы узнаете.

Ссылки

Вот несколько потоков SO, которые предоставляют дополнительную информацию:

Изучение алгоритмов сортировки на языке Java поможет не изобретать велосипеды и быстро выскочить на лесенку карьерного роста.

Задействование алгоритмов сортировки поможет нам упорядочить массивы Java. Для понимания: сортировка чисел от наименьшего к большему или наоборот, а также лексикографический порядок – это примеры алгоритмов сортировки, способные упорядочить Java строки и числа

Слышали о сортировке пузырьком? Его популярность обусловлена простотой, наглядностью и, конечно, названием.

Алгоритм просматривает массив и сравнивает каждую пару соседних элементов. Когда он встречает пару элементов, расположенных не по порядку, происходит замена двух элементов местами.

Остается вопрос: как узнать, что все элементы упорядочены? В этом случае очередная итерация пройдет без замены соседних элементов.

Вот шаги для сортировки массива чисел от наименьшего к большему:

4 2 1 5 3 : два первых элемента расположены в массиве в неверном порядке. Меняем их.
2 4 1 5 3 : вторая пара элементов тоже «не в порядке». Меняем и их.
2 1 4 5 3 : а эти два элемента в верном порядке (4 < 5), поэтому оставляем как есть.
2 1 4 5 3 : очередная замена.
2 1 4 3 5 : результат после одной итерации.

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

Но причём тут пузырьки? Посмотрите снова на пример, и вы увидите, что алгоритм как бы смещается вправо. По этому поведению элементов в массиве и возникла аналогия с «пузырьками», всплывающими на «поверхность».

Реализация

Функция входит в цикл while , в котором проходит весь массив и меняет элементы местами при необходимости.

Массив в алгоритме считается отсортированным. При первой замене доказывается обратное и запускается еще одна итерация.

Цикл останавливается, когда все пары элементов в массиве пропускаются без замен:

Будьте осторожны с формулировкой условия замены!

Например, при условии a[i] >= a[i+1] алгоритм войдет в бесконечный цикл, потому что для равных элементов это условие остается true : отсюда следует бесконечная замена

Временная сложность

Рассмотрим наихудший сценарий. Вот в чем вопрос: сколько итераций нужно для сортировки всего массива? Пример:

При первой итерации 5 «всплывает на поверхность», при этом остальные элементы остаются в порядке убывания. Если вы хотите получить отсортированный массив, придется делать по одной итерации для каждого элемента, кроме 1 , и еще одну итерацию для проверки, что в сумме составляет 5 итераций.

Расширьте это утверждение для массива из n элементов, и получите n итераций. В коде это означает, что цикл while будет запускаться максимум n раз.

Каждая n-ая итерация по всему массиву (цикл for в коде) означает, что временная сложность в наихудшем случае будет равна O(n ^ 2).

Этот алгоритм разделяет оригинальный массив на сортированный и несортированный подмассивы.

Длина сортированной части равна 1 в начале и соответствует первому (левому) элементу в массиве. После этого остается итерировать массив и расширять отсортированную часть массива одним элементом с каждой новой итерацией.

После расширения новый элемент помещается на свое место в отсортированном подмассиве. Это происходит путём сдвига всех элементов вправо, пока не встретится элемент, который не нужно двигать.

В приведенном ниже массиве жирная часть отсортирована в порядке возрастания. Посмотрите что произойдет в этом случае:

3 5 7 8 4 2 1 9 6 : выбираем 4 и помним, что это элемент, который нужно вставить. 8 > 4, поэтому сдвигаем.
3 5 7 x 8 2 1 9 6 : здесь x – нерешающее значение, так как элемент будет перезаписан (на 4, если это подходящее место, или на 7, если смещение). 7 > 4, поэтому сдвигаемся.
3 5 x 7 8 2 1 9 6
3 x 5 7 8 2 1 9 6
3 4 5 7 8 2 1 9 6

Теперь вы видите, что отсортированная часть дополнилась элементом. Каждая следующая итерация делает то же самое, и к концу вы получите отсортированный массив!

Реализация

Временная сложность

Вернемся к худшему сценарию – к массиву, отсортированному в убывающем порядке.

В этом случае каждая итерация сдвигает отсортированный массив на единицу O(n). Придется делать это для каждого элемента в каждом массиве, что приведет к сложности равной O(n ^ 2).

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

3 5 1 2 4
1 5 3 2 4
1 23 5 4
1 2 3 5 4
1 2 3 45
1 2 3 45

Реализация

В каждой итерации вы предполагаете, что первый неотсортированный элемент минимален и итерируете по всем оставшимся элементам в поисках меньшего.

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

Временная сложность

При поиске минимума для длины массива проверяются все элементы, поэтому сложность равна O(n). Поиск минимума для каждого элемента массива равен O(n^2).

Сортировка слиянием эффективнее, чем примеры алгоритмов сортировки, представленные выше, благодаря использованию рекурсии и подходу «разделяй и властвуй».

Массив делится на два подмассива, а затем происходит:

Сортировка левой половины массива (рекурсивно)
Сортировка правой половины массива (рекурсивно)
Слияние

На схеме показана работа рекурсивных вызовов. Для массивов, отмеченных стрелкой вниз, вызывается функция. Во время слияния возвращаются массивы со стрелкой вверх. Всё просто: мы следуем за стрелкой вниз к нижней части дерева, а затем возвращаемся и объединяем.

В примере массив 3 5 4 2 1 делится на 3 5 4 и 2 1 и так далее. При достижении «дна» начинается объединение и сортировка.

Реализация

В главную функцию передаются left и right – индексы подмассивов для сортировки, крайние слева и справа. Изначально они имеют значения 0 и array.length-1 , в зависимости от реализации.

Основа нашей рекурсии гарантирует, что мы выйдем, когда закончим, или когда left и right встретятся друг с другом. Мы находим среднюю точку mid и рекурсивно сортируем подмассивы слева и справа от середины, в итоге объединяя наши решения.

Возможно, вы вспомните дерево и спросите: почему мы не передаем два меньших массива? Ответ прост: это не нужно и вызовет огромное потребление памяти для очень длинных массивов.

Достаточно следовать индексам не нарушая логики дерева рекурсии:

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

После копирования мы проходим по результирующему массиву и назначаем текущий минимум. Помните, что наши подмассивы отсортированы? Теперь нужно просто выбрать наименьший из двух элементов, которые еще не были выбраны, и двигать итератор для этого массива вперед:

Временная сложность

Хотите легко рассчитывать рекурсивные реализации алгоритмов сортировки? Приготовьтесь к математике :)

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

Здесь a – это количество меньших рекурсивных вызовов, на которые мы делим проблему, а b указывает на входную величину рекурсивных вызовов.

Остальная часть уравнения – это сложность слияния всех решений в одно конечное. Упомянутая теорема решит все за вас:

Если T(n) – это время выполнения алгоритма для сортировки массива длинной n , сортировка слиянием запустится дважды для массивов длиной вполовину от оригинального.

Так, если a=2 , b=2 , шаг слияния занимает O(n) памяти при k=1 . Это означает, что уравнение для сортировки слиянием будет выглядеть так:

Примените теорему, и вы увидите, что в нашем случае a=b^k , ибо 2=2^1 . Значит, сложность равна O(nlog n), и это лучшая временная сложность для алгоритма сортировки. Доказано, что массив не может быть отсортирован быстрее, чем O(nlog n).

Для понимания работы пирамидального алгоритма сортировки нужно понять структуру, на которой он основан – пирамиду.

Пирамида или двоичная куча – это дерево, в котором каждый узел состоит в отношениях с дочерними узлами. Добавление нового узла начинается с левой позиции нижнего неполного уровня.

По мере движения вниз по дереву значения уменьшаются (min-heap) или увеличиваются (max-heap). Смотрите пример max-heap:

А теперь представим пирамиду в виде массива:

Чтение графа сверху вниз здесь представлено слева направо. Мы добились того, что позиция дочернего элемента по отношению к k -ому элементу в массиве – 2\*k+1 и 2\*k+2 (при условии, что индексация начинается с 0). Проверьте сами!

И наоборот, для k -го элемента дочерняя позиция всегда равна (k-1)/2 .

С этими знаниями вы сделаете max-heap из любого массива! Для этого проверьте каждый элемент на условие, что каждый из его дочерних элементов имеет меньшее значение.

Условие верно? Тогда меняйте местами один из дочерних элементов с родительским и повторяйте рекурсию с новым родительским элементом (он может всё ещё быть больше другого дочернего).

6 1 8 3 5 2 4 : оба дочерних меньше родительского, оставляем как есть.
6 1 8 3 5 2 4 : 5 > 1, поэтому меняем их. Теперь рекурсивно проверяем 5.
6 5 8 3 1 2 4 : оба дочерних меньше 5, поэтому пропускаем.
65 8 3 1 2 4 : 8 > 6, поэтому меняем их.
8 5 6 3 1 2 4 : мы получили пирамиду, изображенную выше!

Вы научились строить пирамиду из массива, все остальное гораздо проще! Поменяйте местами корень пирамиды с концом массива, и сократите массив на единицу.

Постройте кучу из сокращенного массива и повторяйте процесс:

8 5 6 3 1 2 4
4 5 6 3 1 2 8 : замена
6 5 4 3 1 28 : сортировка
2 5 4 3 1 6 8 : замена
5 2 4 2 16 8 : сортировка
1 2 4 2 5 6 8 : замена

И так далее. Видите закономерность?

Реализация

Временная сложность

Посмотрите на функцию heapify() – кажется, что все делается за O(1), верно? Но нет же: все портит рекурсивный вызов!

Готовы посчитать, сколько вызовов нужно в наихудшем сценарии? В худшем случае рекурсивный вызов дойдет до самой вершины пирамиды прыжками к родителям каждого узла в отношении i/2 . Всего потребуется log n прыжков до вершины, значит, сложность равна O(log n).

В связи с циклами for , которые итерируют весь массив, сложность heapSort() равна O(n). Это дает нам суммарную сложность пирамидальной сортировки O(nlog n).

На этом участнике нашего топа мы закончим разбирать примеры алгоритмов сортировки.

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

Так соблюдается правильная позиция самого «стержня». Затем алгоритм рекурсивно повторяет сортировку для правой и левой частей.

Реализация

Временная сложность

Временную сложность алгоритма быстрой сортировки можно описать следующим уравнением:

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

Получается O(n^2).

На фоне алгоритмов сортировки со сложностью O(nlog n), выглядит не очень :(

На практике быстрая сортировка применяется широко. Судите сами: у алгоритма очень хорошее среднее время запуска, также равное O(nlog n), он эффективен для больших потоков ввода. И на этом преимущества не заканчиваются!

Алгоритм не занимает дополнительного пространства, вся сортировка происходит «на месте», отсутствуют затратные вызовы распределения, из-за чего его часто предпочитают сортировке слиянием.

На этом всё! Не пропустите книги по Java, среди которых Алгоритмы на Java – Роберт Седжвик, Кевин Уэйн – полезная книга для дальнейшего погружения в тему.

У стандартной сортировки (метода sort списка, функции sorted) есть более универсальный способ задания порядка сортировки при помощи параметра key. Значение этого параметра некоторая функция, которая вызывается для каждого элемента, перед сравнением этих элементов: элементы списка сортируются, но сравниваются не значения элементов, а результат вызова переданной функции от этого элемента.

Например, пусть дан список строк, содержащих цифры, нужно упорядочить элементы списка, сравнивая их, как числа, а не как строки. Это можно сделать так:

В качестве параметра передаётся функция int, которая будет использоваться для сравнения элементов, которое теперь будет выполняться в виде int(a[i]) < int(a[j]) . Вместо функции int можно использовать любую другую функцию, которая принимает один аргумент (элемент массива) и возвращает значение, например, если вызвать a.sort(key=len) , то строки будут упорядочены по длине.

В сложных случаях функцию нужно написать самостоятельно, например, пусть дан список чисел, который нужно упорядочить по последней цифре. Напишем функцию, которая возвращает последнюю цифру числа:

Параметр key можно использовать вместе с параметром reverse .

Лямбда-функции

В предыдущем примере пришлось создавать отдельную функцию только для того, чтобы задать порядок сортировки, что захламляет программу ненужными функциями. В таких случаях нужно использовать лямбда-функции: “одноразовые фукцнии, которые можно объявлять без использовать слова def , прямо при вызове сортировки. Лямбда-функция — это функция, которая состоит только из одной строки с инструкцией return , то есть функция сразу возвращает значение по набору аргументов. Лямбда-функции объявляются таким образом:

Например, отсортировать список чисел по последней цифре можно при помощи следующей лямбда-функции:

Рассмотрим другой пример. Пусть дан список точек, каждая точка: кортеж из двух чисел. Например, [(3, -2), (7, 1), (0, 4)] . Этот список нужно отсортировать по возрастанию расстояния от начала координат до точки. Напишем лямбда-функцию:

Элементами списка являются кортежи из двух координат, можно обратиться к этим координатам по индексам [0] и [1].

Устойчивость сортировки

Вернёмся к примеру сортировки по последней цифре. В приведённом выше примере упорядоченный список будет таким:

Этот пример иллюстрирует свойство устойчивости сортировки: функция сортировки не переставлят элементы, если они равны друг другу. В данном случае функция упорядочивает числа по последней цифре, а при равной последней цифре сохраняется порядок следования элементов в исходном списке: 22, 12, 32.

Что делать, если нужно сделать сложную сортировку, учитывающую несколько критериев? Например, при равной последней цифре нужно упорядочить элементы в порядке возрастания самих чисел.

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

Второй способ: воспользуемся устойчивостью сортировки. Отстортируем список сначала по возрастанию чисел, а затем — по последней цифре. Тогда при равном значении последней цифры сохранится ранее полученный порядок.

То есть сортировку по \(k\) параметрам (если по первому параметру элементы равны, то сравнить по второму, если равны два параметра, то сравнить по третьему и т.д.) можно заменить на \(k\) последовательных сортировок, выполняющихся в обратном порядке (от наименее значимого параметра к наиболее значимому).

Функция operator.itemgetter

При сортировке кортежей частой задачей является сортировка по какому-то одному элементу кортежа. Например, если нужно отсортировать кортежи по элементу с индексом 1, то можно написать такую лямбда-функцию:

Для удобства в модуле operator есть функция itemgetter , которая позволяет создавать подобные функции, а именно, функция реализована примерно так:

Лямбда-выражение может быть передано в метод в качестве аргумента. Объявление такого метода должно содержать ссылку на соответствующий функциональный интерфейс. Эта ссылка получается параметром метода, который обрабатывает лямбда-выражение.

Существует два способа передачи лямбда-выражения в метод:

непосредственная передача лямбда-выражения. Этот способ хорошо подходит для лямбда-выражений с малым количеством операторов;
передача ссылки на функциональный интерфейс, который связан с лямбда-выражением. В этом случае предварительно объявляется ссылка на интерфейс. Затем этой ссылке присваивается код лямбда-выражения. Этот способ уместен, когда лямбда-выражение становится слишком длинным для встраивания в вызов метода.

2. Пример, демонстрирующий способы передачи лямбда-выражения в метод

Пусть требуется передать в метод лямбда-выражение, которое находит среднее арифметическое трех чисел. Для этого выполняется следующая последовательность шагов.

Способ 1. Сначала объявляется функциональный интерфейс IAverage , содержащий метод, который получает три параметра и возвращает результат типа double

Следующим шагом нужно объявить метод, который будет получать ссылку на интерфейс IAverage в качестве параметра. Этот метод может быть размещен в некотором классе как показано ниже

Способ 2. При этом способе предварительно формируется ссылка на интерфейс. Затем этой ссылке присваивается лямбда-выражение. После этого эта ссылка передается в метод PrintAverage() . Такой подход полезен, когда код лямбда-выражения слишком большой и усложняет восприятие вызова метода. Далее приведен измененный код предыдущего примера.

3. Примеры решения задач, в которых лямбда-выражение передается в качестве аргумента метода

3.1. Максимальное значение в массиве чисел. Шаблонный функциональный интерфейс. Передача лямбда-выражения в статический метод

Условие задачи. Разработать лямбда-выражение, которое находит максимальное значение в массиве чисел, имеющих некоторый числовой тип T . Реализовать передачу лямбда-выражения в статический метод. В методе вывести максимальное значение на экран.

Решение. В задаче объявляется обобщенный (шаблонный) функциональный интерфейс IArray . В интерфейсе определен один метод, который получает массив чисел типа T и возвращает значение типа T .
Класс Lambda является основным классом в программе, который содержит функцию main() . В функции main() формируются:

лямбда-выражение, вычисляющее максимальное значение в массиве A , которое является входным параметром. Следует обратить внимание, что массив A указывается параметром лямбда-выражения без скобок [ ] ;
массив целых чисел, который передается в статический метод Solution() .

С целью демонстрации, в классе Lambda реализовано статический шаблонный метод Solution() , который получает два параметра:

массив обобщенного типа T , в котором нужно найти максимальный элемент;
лямбда-выражение, которое передается в метод как ссылка ref на функциональный интерфейс IArray .

Текст решения задачи следующий

Результат работы программы

3.2. Сортировка массива строк методом вставки. Алгоритм сортировки передается лямбда-выражением

В примере демонстрируется использование лямбда-выражения для сортировки массива строк методом вставки.

Результат выполнения программы

3.3. Вычисление количества вхождений элемента в массиве. Обобщенный функциональный интерфейс

Реализовать лямбда-выражение, которое определяет количество вхождений элемента в массиве. Лямбда-выражение реализует обобщенный функциональный интерфейс.

Реализовать метод класса, который получает лямбда-выражение в качестве параметра и выводит количество вхождений элемента в массиве.

Читайте также: