Способы сортировки массива 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() сортирует только примитивные типы данных и строки. Как сортировать массив из собственно созданных объектов, будет рассмотрено в следующих уроках, поскольку это требует более углубленных знаний.

есть ли простой способ отсортировать массив в порядке убывания, например, как у них есть сортировка в порядке возрастания в массивы класс?

или я должен перестать лениться и сделать это сам: [

14 ответов

вы можете использовать это для сортировки всех видов объектов

Arrays.sort() нельзя использовать напрямую для сортировки примитивных массивов в порядке убывания. Если вы попытаетесь вызвать Arrays.sort() метод путем проходить обратный компаратор определенный Collection.reverseOrder() , он будет бросать ошибку

нет подходящего метода для сортировки (int[],comparator)

это будет отлично работать с целочисленным массивом, но не будет работать с массивом int.

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

вы можете использовать это:

Collections.reverseOrder() возвращает Comparator используя обратный порядок. Вы можете получить перевернутую версию собственного компаратора, используя Collections.reverseOrder(myComparator) .

без явного компаратор:

с явными компаратор:

альтернативой может быть (для цифры. )

  1. умножение массива на -1
  2. вроде
  3. умножьте еще раз на -1

обновление: reversed() реверсирует указанный компаратор. Обычно компараторы упорядочивают по возрастанию, поэтому это изменяет порядок на нисходящий.

для массива, который содержит элементы примитивов, если есть org.apache.commons.lang(3) в распоряжении простой способ обратить массив (после его сортировки) – использовать:

Я не знаю, каков был ваш вариант использования, однако в дополнение к другим ответам здесь другой (ленивый) вариант-все еще сортировать в порядке возрастания, как вы указываете, но затем повторять в реверс порядок.

сначала нужно отсортировать массив, используя:

затем вам нужно изменить порядок от восходящего к нисходящему, используя:

еще один решение заключается в том, что если вы используете сравнима интерфейс вы можете переключать выходные значения, которые вы указали в своем compareTo (Object bCompared).

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

чтобы использовать этот compareTo, мы просто называем Arrays.sort(mFreq) , который даст вам в отсортированном массиве freq [] mFreq .

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

Читайте также:  Таблица прошиваемых ps3 slim

просто используйте этот метод для сортировки массива типа double в порядке убывания, вы можете использовать его для сортировки массивов любых других типов (например, int, float и т. д.), просто изменив "тип возврата", "тип аргумента" и переменную "x" на соответствующий тип. вы также можете изменить "> = " на "

Я знаю, что это очень старая нить, но вот обновленная версия для целых чисел и Java 8:

обратите внимание, что это" o1 – o2 " для нормального восходящего порядка (или компаратора.comparingInt ()).

Это также работает для любых других видов объектов. Скажи:

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

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

Сортировка массива используется в реальных проектах чаще, чем Вы это можете представить. Например, файловому менеджеру необходимо отсортировать отображаемые файлы по имени, чтобы пользователь мог легко перемещаться по ним. Или, еще один пример, в видеоигре может понадобиться сортировка 3D-объектов, отображаемых в мире, на основе их расстояния от глаза игрока в виртуальном мире, чтобы определить, что видимо, а что нет. Объекты, которые оказываются ближе всего к игроку видны, а те, которые находятся дальше, могут скрываться.

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

  1. Находим номер минимального значения в текущем списке;
  2. Производим обмен этого значения со значением первой не отсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции);
  3. Теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы.

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

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

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

Читайте также:  Драйвер для телевизора сони

Вот его код на Java:

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

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

Время сортировки вставками зависит от массива. Чем больше сортируемый массив, тем больше может понадобиться времени для его сортировки. Причем здесь, как Вы могли заметить, важен не только размер, но и входной массив. Если Вы читали предыдущий материал о сложности алгоритма, то можете посчитать, что его сложность составляет О(n)= что не очень хорошо для алгоритма. Этот алгоритм используется как часть алгоритма сортировки Шелла.

При сортировке Шелла сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии d. Выбор d – как последовательность чисел Фибоначчи. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d=1 (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

Догодуюсь, что немного непонятно. Попробую привести пример. Пусть дан список A = (32, 95, 16, 82, 24, 66, 35, 19, 75, 54, 40, 43, 93, 68) и выполняется его сортировка методом Шелла, а в качестве значений d выбраны 5, 3, 1.
На первом шаге сортируются подмассивы A, составленные из всех элементов A, различающихся на 5 позиций, то есть подмассивы A_ <5,1>= (32, 66, 40), A_ <5, 2>= (95, 35, 43), A_ <5, 3>= (16, 19, 93), A_ <5, 4>= (82, 75, 68), A_ <5, 5>= (24, 54).
В полученном массиве на втором шаге вновь сортируются подмассивы из отстоящих на 3 позиции элементов. Процесс завершается обычной сортировкой вставками получившегося списка.