Sort array in java program

Алгоритмы сортировки на Java с примерами

В одной из предыдущих статей мы разобрались, где применяются алгоритмы сортировки, а теперь поговорим об их реализации на Java. Помните, что разные алгоритмы оптимальны для разных наборов и типов данных. В нашей статье мы рассмотрим наиболее «ходовые».

Алгоритм сортировки пузырьком на Java

Сортировка пузырьком (Bubble Sort) — это один из наиболее известных алгоритмов, суть которого состоит в последовательном сравнении двух соседних элементов. В том случае, если предыдущий элемент больше последующего, они меняются местами.

Так выглядит сортировка пузырьком на Java:

public static void bubbleSort(int[] sortArr) < for (int i = 0; i < sortArr.length - 1; i++) < for(int j = 0; j < sortArr.length - i - 1; j++) < if(sortArr[j + 1] < sortArr[j]) < int swap = sortArr[j]; sortArr[j] = sortArr[j + 1]; sortArr[j + 1] = swap; >> > > public static void main(String args[]) < int[] sortArr = ; bubbleSort(sortArr); for(int i = 0; i < sortArr.length; i++)< System.out.print(sortArr[i] + "\n"); >>

Объяснение

Как видим из кода, метод bubbleSort() принимает массив в качестве входных данных для сортировки — sortArr . Далее мы создаём внешний цикл for , который перебирает каждый элемент массива, тогда как внутренний цикл for начинается с первого элемента массива до предпоследнего индекса: sortArr.length — i — 1 . С помощью условия if мы проверяем, больше ли элемент слева элемента справа или нет. Если элемент слева действительно больше, он меняется местами с правым элементом.

Примечание Внешний цикл for будет перебирать все элементы массива, даже если массив уже полностью отсортирован.

Массив, который принимает метод bubbleSort() , может быть любым. В нашем примере мы передаём значения 12, 6, 4, 1, 15, 10 .

Сложность алгоритма: О(n2)

А ниже представлен алгоритм сортировки двумерного массива Java пузырьком:

public static int[][] matrixBubbleSort(int[][] sortMatrix) < int swap; for (int i = 0; i < sortMatrix.length; i++) < for (int j = 0; j < sortMatrix[i].length; j++) < for (int k = 0; k < sortMatrix.length; k++) < for (int l = 0; l < sortMatrix[k].length; l++) < if (sortMatrix[i][j] > > > > return sortMatrix; > public static void main(String args[]) < int[][] sortMatrix = new int[][]< , , >; matrixBubbleSort(sortMatrix); //Вывод отсортированного двумерного массива: for (int i = 0; i < sortMatrix.length; i++) < for (int j = 0; j < sortMatrix[i].length; j++) < System.out.print(sortMatrix[i][j] + " "); >System.out.println(); > >

Алгоритм быстрой сортировки на Java

Быстрая сортировка, также известная как Quick Sort или сортировка Хоара, является одним их самых эффективных алгоритмов. Она включает в себя три этапа:

1. Из массива выбирается опорный элемент, чаще всего посередине массива.
2. Другие элементы массива распределяются таким образом, чтобы меньшие размещались до него, а большие — после.
3. Далее первые шаги рекурсивно применяются к подмассивам, которые разделились опорным элементом на две части — слева и справа от него.

Пример быстрой сортировки на языке Java:

public static void quickSort(int[] sortArr, int low, int high) < //завершить,если массив пуст или уже нечего делить if (sortArr.length == 0 || low >= high) return; //выбираем опорный элемент int middle = low + (high - low) / 2; int border = sortArr[middle]; //разделияем на подмассивы и меняем местами int i = low, j = high; while (i border) j--; if (i > //рекурсия для сортировки левой и правой части if (low < j) quickSort(sortArr, low, j); if (high >i) quickSort(sortArr, i, high); > public static void main(String args[]) < int[] sortArr = ; quickSort(sortArr, 0, sortArr.length - 1); for(int i = 0; i < sortArr.length; i++)< System.out.print(sortArr[i] + "\n"); >>

Сложность алгоритма: O(n log n)

Алгоритм сортировки слиянием на Java

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

Примечание По возможности используйте готовые алгоритмы для коллекций и методы из java.util.Arrays .

Реализовать алгоритм сортировки слиянием на Java можно так:

import java.util.Arrays; public class Main < public static int[] mergeSort(int[] sortArr) < int[] buffer1 = Arrays.copyOf(sortArr, sortArr.length); int[] buffer2 = new int[sortArr.length]; int[] result = mergeSortInner(buffer1, buffer2, 0, sortArr.length); return result; >public static int[] mergeSortInner(int[] buffer1, int[] buffer2, int startIndex, int endIndex) < if (startIndex >= endIndex - 1) < return buffer1; >//уже отсортирован int middle = startIndex + (endIndex - startIndex) / 2; int[] sorted1 = mergeSortInner(buffer1, buffer2, startIndex, middle); int[] sorted2 = mergeSortInner(buffer1, buffer2, middle, endIndex); //слияние int index1 = startIndex; int index2 = middle; int destIndex = startIndex; int[] result = sorted1 == buffer1 ? buffer2 : buffer1; while (index1 < middle && index2 < endIndex) < result[destIndex++] = sorted1[index1] < sorted2[index2] ? sorted1[index1++] : sorted2[index2++]; >while (index1 < middle) < result[destIndex++] = sorted1[index1++]; >while (index2 < endIndex) < result[destIndex++] = sorted2[index2++]; >return result; > public static void main(String args[]) < int[] sortArr = ; int[] result = mergeSort(sortArr); System.out.println(Arrays.toString(result)); > >

Объяснение

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

Сложность алгоритма: O(n log n)

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

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

Так выглядит сортировка вставками на Java:

public static void insertionSort(int[] sortArr) < int j; //сортировку начинаем со второго элемента, т.к. считается, что первый элемент уже отсортирован for (int i = 1; i < sortArr.length; i++) < //сохраняем ссылку на индекс предыдущего элемента int swap = sortArr[i]; for (j = i; j >0 && swap < sortArr[j - 1]; j--) < //элементы отсортированного сегмента перемещаем вперёд, если они больше элемента для вставки sortArr[j] = sortArr[j - 1]; >sortArr[j] = swap; > > public static void main(String args[]) < int[] sortArr = ; insertionSort(sortArr); for(int i = 0; i < sortArr.length; i++)< System.out.print(sortArr[i] + "\n"); >>

Объяснение

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

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

Сложность алгоритма: О(n2) для сравнений и перестановок.

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

1. Разбиваем массив на отсортированную и неотсортированную части.
2. Находим в неотсортированной части минимальный элемент.
3. Меняем его местами с тем элементом, который находится на нулевой позиции —
   в конец отсортированного массива.
4. Далее находим следующий по величине элемент и меняем его с элементом на первой позиции, etc., пока не закончатся неотсортированные значения.

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

public static void selectionSort(int[] sortArr) < for (int i = 0; i < sortArr.length; i++) < int pos = i; int min = sortArr[i]; //цикл выбора наименьшего элемента for (int j = i + 1; j < sortArr.length; j++) < if (sortArr[j] < min) < //pos - индекс наименьшего элемента pos = j; min = sortArr[j]; >> sortArr[pos] = sortArr[i]; //меняем местами наименьший с sortArr[i] sortArr[i] = min; > > public static void main(String args[]) < int[] sortArr = ; selectionSort(sortArr); for(int i = 0; i < sortArr.length; i++)< System.out.print(sortArr[i] + "\n"); >>

Сложность алгоритма: О(n2)

Алгоритм пирамидальной сортировки на Java

Чтобы реализовать алгоритм пирамидальной сортировки (Heapsort) на Java, нужно сперва понять принцип. Алгоритм сегментирует массив на отсортированный и неотсортированный. Неотсортированный сегмент преобразовывается в кучу (heap), что позволяет эффективно эффективно определить самый большой элемент.

Пирамидальная сортировка на Java с использованием класса java.util.Arrays :

//вернуть левого потомка `A[i]` private static int LEFT(int i) < return (2 * i + 1); >//вернуть правого потомка `A[i]` private static int RIGHT(int i) < return (2 * i + 2); >//вспомогательная функция для замены двух индексов в массиве private static void swap(int[] sortArr, int i, int j) < int swap = sortArr[i]; sortArr[i] = sortArr[j]; sortArr[j] = swap; >//рекурсивный алгоритм heapify-down. Узел с индексом `i` и 2 его прямых потомка нарушают свойство кучи private static void heapify(int[] sortArr, int i, int size) < // получить левый и правый потомки узла с индексом `i` int left = LEFT(i); int right = RIGHT(i); int largest = i; //сравниваем `A[i]` с его левым и правым дочерними элементами и находим наибольшее значение if (left < size && sortArr[left] >sortArr[i]) largest = left; if (right < size && sortArr[right] >sortArr[largest]) largest = right; //поменяться местами с потомком, имеющим большее значение и вызовите heapify-down для дочернего элемента if (largest != i) < swap(sortArr, i, largest); heapify(sortArr, largest, size); >> //функция для удаления элемента с наивысшим приоритетом (присутствует в корне) public static int pop(int[] sortArr, int size) < //если в куче нет элементов if (size int top = sortArr[0]; //заменяем корень кучи последним элементом массива sortArr[0] = sortArr[size-1]; //вызовите heapify-down на корневом узле heapify(sortArr, 0, size - 1); return top; > //функция для выполнения пирамидальной сортировки массива `A` размера `n` public static void heapSort(int[] sortArr) < //строим приоритетную очередь и инициализируем ее заданным массивом int n = sortArr.length; //build-heap: вызывать heapify, начиная с последнего внутреннего //узел до корневого узла int i = (n - 2) / 2; while (i >= 0) < heapify(sortArr, i--, n); >//несколько раз извлекаем из кучи, пока она не станет пустой while (n > 0) < sortArr[n - 1] = pop(sortArr, n); n--; >> public static void main(String args[]) < int[] sortArr = ; heapSort(sortArr); for(int i = 0; i < sortArr.length; i++)< System.out.print(sortArr[i] + "\n"); >>

Сложность алгоритма: O(n log n)

Источник

Sorting Arrays in Java

Learn to sort a Java array of primitives, strings and custom objects in multiple ways with the help of Comparable and Comparator interfaces, Arrays.sort() and Stream.sorted() APIs.

We will learn to sort arrays in natural ordering, reverse ordering and any other custom ordering as well.

1. Basics of Array Sorting

The basic concepts behind the sorting feature remain the same no matter which Java API we use to sort.

• All inbuilt APIs support the sorting with the natural order by default. Numerical types are sorted in ascending order, strings are sorted in dictionary order (lexicographically) and custom objects are sorted by the order implemented by the Comparable interface.
• To sort in the reverse order, we can use Comparator.reverseOrder() to the sort methods.
• To sort in the custom order, we must create an instance of the Comparator interface and provide the relevant sorting behavior in it. Then we will pass an instance of the comparator into the sort API.

Now let’s dive into the java programs demonstrating the sorting of arrays. For custom sorting, we will use the instances of User class. Note that the default sorting is supported on the id field.

public class User implements Comparable  < public long id; public String firstName; public String lastName; //Add getters and setters @Override public int compareTo(final User user) < if(user == null ) < return -1; >else < return (int)(this.id - user.id); >> >

2. Arrays.sort() and Arrays.parallelSort()

The java.util.Arrays class provides many utilities static methods. The sort() APis are also such methods that helps in sorting a given array of items.

The sort() API implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted. It offers the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons.

The parallelSort() API implementation is a Dual-Pivot quicksort that offers O(n log(n)) performance on all data sets, and is typically faster than traditional (one-pivot) quicksort implementations.

public static void sort(array, ?comparator) public static void parallelSort(array, ?comparator)

2.1. Sorting in Natural Order

Java program to sort a String array in default order. Note that String class has implemented the Comparable interface, already.

String[] tokens = ; Arrays.sort(tokens); //[A, B, C, D, E]

2.2. Sorting in Reverse Order

Java program to use the Comparator.reverseOrder() to reverse the natural ordering.

String[] tokens = ; Arrays.sort(tokens, Collections.reverseOrder()); //[E, D, C, B, A]

We are sorting the users array by their first name.

User[] users = getUsersArray(); Comparator firstNameSorter = Comparator.comparing(User::getFirstName); Arrays.sort(users, firstNameSorter);

To sort on multiple fields, like SQL group by clause, we can create a complex Comparator instance and use it for sorting purposes.

Comparator fullNameSorter = Comparator.comparing(Employee::getFirstName) .thenComparing(Employee::getLastName); Arrays.sort(employees, fullNameSorter);

3. Sorting Arrays using Stream API

We can sort the array of primitives or custom objects using the Stream.sorted() method in a very similar way we used the Arrays.sort() API.

• The sorted() API returns a stream consisting of the elements of this stream, sorted according to the natural order.
• If the elements of this stream are not Comparable , a java.lang.ClassCastException may be thrown when the terminal operation is executed.
• It also accepts an optional comparator instance that is used for implementing the custom sorting behavior.

For ordered streams (stream is generated from an ordered collection such as ArrayList), the sort is stable. For unordered streams (for example, streams generated from HashMap), no stability guarantees are made.

Stream sorted() Stream sorted(?comparator)

//1. Natural ordering User[] sortedUserArray = Stream.of(userArray) .sorted() .toArray(User[]::new); //2. Reverse ordering User[] sortedUserArray = Stream.of(userArray) .sorted(Comparator.reverseOrder()) .toArray(User[]::new); //3. Custom Sorting Comparator nameComparator = Comparator.comparing(Employee::getName) .thenComparing(Employee::getId) User[] sortedUserArray = Stream.of(userArray) .sorted(nameComparator) .toArray(User[]::new);

In this given example, we learned to sort an array using Arrays.sort() and Stream APIs. We learned to sort in natural order, reverse order as well as in custom order.

Источник

Sort array in java program

Learn Latest Tutorials

Preparation

Trending Technologies

B.Tech / MCA

Javatpoint Services

JavaTpoint offers too many high quality services. Mail us on h[email protected], to get more information about given services.

• Website Designing
• Website Development
• Java Development
• PHP Development
• WordPress
• Graphic Designing
• Logo
• Digital Marketing
• On Page and Off Page SEO
• PPC
• Content Development
• Corporate Training
• Classroom and Online Training
• Data Entry

Training For College Campus

JavaTpoint offers college campus training on Core Java, Advance Java, .Net, Android, Hadoop, PHP, Web Technology and Python. Please mail your requirement at [email protected].
Duration: 1 week to 2 week

Like/Subscribe us for latest updates or newsletter

Источник