Как отсортировать массив чисел java

Как отсортировать массив чисел java

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

Если тема для вас новая, и вы еще не знакомы с алгоритмами сортировки, то наверняка при решении задачи «Отсортировать массив по возрастанию» первое что придет в голову, это перебор, то есть: найти минимальный элемент и поменять его местами с начальным, потом, в оставшейся части массива (кроме первого элемента), найти снова минимальный элемент и поменять его со вторым элементом и т.д. Такой алгоритм называется Сортировка выбором. Рассмотрим его подробнее.

Сортировка выбором (Selection sort) в Java.

Реализация алгоритма Сортировка выбором на Java:

Еще одним достаточно простым и известным способом сортировки является Сортировка пузырьком.

Сортировка пузырьком (Bubble sort) в Java.

Алгоритм проходит массив от начала и до конца, сравнивая попарно соседние элементы, Если элементы стоят в неправильном порядке, то они меняются местами, таким образом, после первого прохода на конце массива оказывается максимальный элемент (для сортировки по возрастанию). Затем проход массива повторяется, и на предпоследнем месте оказывается другой наибольший после максимального элемент и т.д. В итоге, наименьший элемент постепенно перемещается к началу массива («всплывает» до нужной позиции как пузырёк в воде).

Реализация алгоритма Сортировка пузырьком на Java (по возрастанию):

Следующие 2 видео наглядно демонстрируют работу алгоритмов сортировки пузырьком и выбором.

Рассмотрим примеры того, как можно воспользоваться выше приведенными алгоритмами.
Для начала создадим массив. Это можно сделать так:

Или мы можем создать массив случайных чисел

Затем воспользуемся вышеприведенными алгоритмами сортировки

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

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

Сортировка массива при помощи метода sort() из класса Arrays.

Метод sort() из класса Arrays использует усовершенствованный алгоритм Быстрой сортировки (Quicksort), который эффективен в большинстве случаев. Для того чтобы отсортировать массив, необходимо написать всего одну строку.

Примечание: в начале файла предварительно нужно подключить библиотеку java.util.

Сортировка массива целых чисел по возрастанию:

Сортировка массива целых чисел по убыванию:

Обратите внимание, что при сортировке массива в обратном порядке (по убыванию) нужно использовать тип Integer[] вместо примитивного типа int[].

Сортировка массива строк в Java:

В этом примере массив имен сортируется в порядке от А до Я. Для того чтобы отсортировать массив в обратном порядке, необходимо в методе sort() указать Collections.reverseOrder().

К сожалению, по умолчанию метод sort() сортирует только примитивные типы данных и строки. Как сортировать массив из собственно созданных объектов, будет рассмотрено в следующих уроках, поскольку это требует более углубленных знаний.

Источник

Алгоритмы сортировки в Java

В этом уроке мы реализуем множество алгоритмов сортировки на Java с примерами. Это включает в себя Сортировку пузырьков, Сортировку вставки, Сортировку выбора, Сортировку слиянием, Сортировку по кучам и Быструю сортировку.

Вступление

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

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

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

Примечание : Эта статья не будет посвящена параллельной сортировке, так как она предназначена для начинающих.

Сортировка Пузырьков

Объяснение

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

Мы знаем, что все элементы в порядке, когда нам удается выполнить всю итерацию вообще без замены – тогда все элементы, которые мы сравнивали, находились в нужном порядке с их соседними элементами и, как следствие, со всем массивом.

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

4 2 1 5 3: Первые два элемента расположены в неправильном порядке, поэтому мы меняем их местами.

2 4 1 5 3: Вторые два элемента тоже расположены в неправильном порядке, поэтому мы меняемся местами.

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

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

На первой итерации 5 “всплывет на поверхность”, но остальные элементы останутся в порядке убывания. Нам пришлось бы выполнить одну итерацию для каждого элемента, кроме 1, а затем еще одну итерацию, чтобы проверить, все ли в порядке, так что в общей сложности 5 итераций.

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

Сортировка Вставки

Объяснение

Идея сортировки вставки заключается в разделении массива на отсортированные и несортированные подмассивы.

Отсортированная часть имеет длину 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

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

Реализация

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

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

Сортировка выбора

Объяснение

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

1 5 3 2 4

1 2 3 5 4

1 2 3 5 4

1 2 3 4 5

1 2 3 4 5

Реализация

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

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

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

Сортировка слиянием

Объяснение

Используя обе эти концепции, мы разобьем весь массив на два подмассива, а затем:

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

Реализация

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

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

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

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

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

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

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

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

Само уравнение рекурсивно! В этом уравнении a сообщает нам, сколько раз мы вызываем рекурсию, и b сообщает нам, на сколько частей разделена наша проблема. В данном случае это может показаться несущественным различием, потому что они равны для сортировки слиянием, но для некоторых проблем это может быть не так.

Остальная часть уравнения-это сложность объединения всех этих решений в одно в конце. Главная теорема решает это уравнение за нас:

Git Essentials

Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

Хотя версия, которую мы продемонстрировали, требует много памяти, существуют более сложные версии сортировки слиянием, которые занимают только O(1) пространство.

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

Объяснение

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

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

Мы можем представить эту максимальную кучу в памяти в виде массива следующим образом:

Вы можете представить это как чтение с графика уровень за уровнем, слева направо. Таким образом, мы добились того, что если мы возьмем k-й элемент в массиве, его дочерние позиции будут 2*k+1 и 2*k+2 (при условии, что индексация начинается с 0). Вы можете проверить это сами.

Зная это, вы можете легко “максимизировать” любой заданный массив. Для каждого элемента проверьте, не меньше ли его дочерних элементов. Если это так, замените один из них родительским и рекурсивно повторите этот шаг с родителем (потому что новый большой элемент все равно может быть больше, чем его другой дочерний элемент).

У листьев нет детей, поэтому они тривиально максимальные кучи свои собственные:

6 1 8 3 5 2 4 : Оба ребенка меньше, чем родитель, поэтому все остается по-прежнему.

6 1 8 3 5 2 4: Поскольку 5 > 1, мы меняем их местами. Теперь мы рекурсивно накапливаем 5.

6 5 8 3 1 2 4: Оба ребенка меньше, так что ничего не происходит.

6 5 8 3 1 2 4: Поскольку 8 > 6, мы меняем их местами.

8 5 6 3 1 2 4: У нас есть куча, изображенная выше!

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

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

4 5 6 3 1 2 8 : поменялись местами

6 5 4 3 1 2 8 : наваленные

2 5 4 3 1 6 8 : поменялись местами

5 2 4 2 1 6 8 : наваленные

1 2 4 2 5 6 8 : поменялись местами

И так далее, я уверен, вы видите, как складывается картина.

Реализация

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

Heapsort-это сортировка на месте, то есть она занимает O(1) дополнительное пространство, в отличие от сортировки слиянием, но у нее также есть некоторые недостатки, такие как сложность распараллеливания.

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

Объяснение

Быстрая сортировка-это еще один алгоритм “Разделяй и властвуй”. Он выбирает один элемент массива в качестве оси и сортирует все остальные элементы вокруг него, например, меньшие элементы слева и большие справа.

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

Реализация

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

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

Наихудший сценарий-это когда самый большой или самый маленький элемент всегда выбирается для pivot. Тогда уравнение будет выглядеть следующим образом:

Это может показаться плохим, так как мы уже изучили несколько алгоритмов, которые выполняются в O(nlogn) время в худшем случае, но на самом деле Quicksort используется очень широко.

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

Сравнение Производительности

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

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

Давайте запустим все реализации, одну за другой, каждую на копии перемешанного массива из 10 000 целых чисел:

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

Сортировка на Java

Сопоставимый Интерфейс

Если у вас есть свои собственные типы, может оказаться затруднительным реализовать отдельный алгоритм сортировки для каждого из них. Вот почему Java предоставляет интерфейс, позволяющий использовать Collections.sort() в ваших собственных классах.

Этот метод возвращает отрицательное целое число, если это меньше элемента аргумента, 0, если они равны, и положительное целое число, если это больше.

Мы хотим отсортировать их в первую очередь по поколениям, но также и во вторую очередь по идентификаторам:

И вот как его использовать в приложении:

Интерфейс компаратора

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

Если мы заменим вызов сортировки в main следующим:

Как все это Работает

Вывод

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

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

Источник

WebEx

Блог Александра Богомолова

Топ 10 алгоритмов сотрировки в Java

Алгоритмы сортировки это алгоритмы которые вставляют элементы в список в определенном порядке.
Наиболее используемые это числовая и лексикографическая сортировки.
Класс Arrays в Java Collections содержит перегруженный метод sort() для сортировки примитивных типов данных и объектов.

Аналогично мы можем отсортировать коллекцию используя метод Collections.sort().
Но если нам надо отсортировать данные без использования библиотечных методов, мы можем использовать популярные алгоритмы сортировки реализованные на Java.

Простая сортировка

Сортировка выбором

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

Вывод: 1 2 3 4 5 6 7 8 9 10

Сортировка вставкой

Алгоритм сортировки вставкой просматривает данные в виде двух половинок.
Левая половина отсортированных элементов, правая которые нужно отсортировать.
В каждой итерации, один элемент из правой половины берется и добавляется в левую половину так, что левая половина по-прежнему остается отсортированной.
Сортировка вставкой сортирует за время О(n²)

Ввод: int[] elements = < 3, 2, 5, 7, 1,9>;

Вывод: 1 2 3 5 7 9

Но что если нам надо отсортировать массив строк?
Мы можем изменить логику сравнения в цикле и использовать метод compareTo(). Этот метод может принимать любой массив элементов реализующих интерфейс Comparable.

Вывод: Com, Dot, Http, Java, Top, Tutorial

Эффективная сортировка

Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»)

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

Вывод: 2 12 15 16 23 27 34 45 53 56 78 91

Сортировка слиянием

Сортировка слияние один из наиболее популярных алгоритмов в Java так как использует наименьшее количество сравнений.
Сортировка слиянием используется в стандартных Java библиотеках для сортировки generic.
Идеей сортировки слиянием является то, что происходит слияние двух отсортированных списков.
Сортировка слиянием занимает O(nlogn).

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

Сортировка слиянием в Java:

Вывод: 1 2 3 4 5 6 7 8 9 10

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

Быстрая сортировка это алгоритм быстрой сортировки. Его среднее время O(N logN), наихудшее O(N²).

Вывод: 1 2 3 4 5 6 7 8 9 10

Пузырьковая сортировка и варианты

Пузырьковая сортировка в Java

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

Вывод: 1 2 3 4 5 6 7 8 9 10

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

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

Вывод: 1 2 3 4 5 6 7 8 9 10

Распределенная сортировка

Блочная сортировка (bucket sort)

Алгоритм блочной сортировки распределяет элементы массива в некоторое число блоков. Это сортировка без сравнения.

Работает блочная сортировка следующим образом:

Вывод: 1 2 3 4 5 6 7 8 9 10

Поразрядная сортировка (radix sort)

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

Есть два основных типа поразрядной сортировки:

Вывод: 2 3 23 24 44 45 66 75 90 170 232 234 802

Сортировка подсчетом

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

Вывод: 1 2 3 4 5 6 7 8 9 10

Источник