Сортировка одномерного массива на java

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

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

int[] intArray = ; Arrays.sort(intArray);

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

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

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

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

package com.topjavatutorial; public class ExampleSelectionSort < public static void main(String[] args) < // TODO Auto-generated method stub int[] numbers = < 3, 6, 1, 7, 2, 8, 10, 4, 9, 5 >; int n = numbers.length; selectionSort(numbers, 0, n - 1); for (int i = 0; i < n; i++) System.out.print(numbers[i] + " "); >// Selection sort algorithm public static void selectionSort(int[] numbers, int low, int high) < for (int h = low; h // Get the position of the smallest value from numbers[low] to numbers[high] public static int getSmallest(int[] numbers, int low, int high) < int small = low; for (int i = low + 1; i // swap numbers public static void swap(int[] numbers, int i, int j) < int temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; >>

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

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

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

private void insertionSort(int[] elements) < for (int i = 1; i < elements.length; i++) < int key = elements[i]; int j = i - 1; while (j >= 0 && key < elements[j]) < elements[j + 1] = elements[j]; j--; >// end while loop elements[j + 1] = key; >// end for loop >

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

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

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

private static void insertionSort(String[] elements) < for (int i = 1; i < elements.length; i++) < String key = elements[i]; int j = i - 1; while (j >= 0 && (key.compareTo(elements[j]) < 0)) < elements[j + 1] = elements[j]; j--; >// end while loop elements[j + 1] = key; >// end for loop >

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

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

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

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

package com.topjavatutorial; public class ExampleHeapSort < public static void main(String[] args) < // TODO Auto-generated method stub int[] numbers = < 12, 2, 15, 56, 23, 78, 45, 34, 16, 91, 53, 27 >; heapsort(numbers); for (int h = 0; h < numbers.length; h++) System.out.print(numbers[h]+ " "); >// sort num[1] to num[n] public static void heapsort(int[] a) < for (int i = a.length / 2 - 1; i >= 0; i--) // convert the array to a heap shiftDown(a, i, a.length); for (int i = a.length - 1; i > 0; i--) < swap(a, 0, i); /* deleteMax */ shiftDown(a, 0, i); >> // end heapSort private static void shiftDown(int[] a, int i, int n) < int child; int tmp; for (tmp = a[i]; leftChild(i) < n; i = child) < child = leftChild(i); if (child != n - 1 && (a[child] < a[child + 1])) child++; if (tmp < a[child]) a[i] = a[child]; else break; >a[i] = tmp; > private static int leftChild(int i) < return 2 * i + 1; >// swap numbers public static void swap(int[] numbers, int i, int j) < int temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; >> // end class ExampleHeapSort

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

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

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

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

Start merge sort sort first half (recursive) sort second half(recursive) merge sorted halves into one sorted list End sort

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

package com.topjavatutorial; public class ExampleMergeSort < public static void main(String[] args) < // TODO Auto-generated method stub int[] num = < 3,6,1,7,2,8,10,4,9,5>; int n = num.length; mergeSort(num, 0, n - 1); for (int h = 0; h < n; h++) System.out.print(num[h]+ " "); >/* * Internal method that makes recursive calls to sort the data * elements is the array of elements to be sorted * low is the left most position of the array * high is the right most position of the array */ public static void mergeSort(int[] elements, int low, int high) < if (low < high) < // list contains at least 2 elements int mid = (low + high) / 2; mergeSort(elements, low, mid); // recursion : sort first half mergeSort(elements, mid + 1, high); // recursion : sort second half merge(elements, low, mid, high); // merge both sorted halves >> /* * Merge sorted array of elements from low to mid and mid+1 * low is the left most position of the subset of elements * high is the right most position of the subset of elements */ private static void merge(int[] subset, int low, int mid, int high) < int n = high-low+1; int[] Temp = new int[n]; int i = low, j = mid + 1; int k = 0; while (i mid) Temp[k++] = subset[j++]; else if (j > high) Temp[k++] = subset[i++]; else if (subset[i] < subset[j]) Temp[k++] = subset[i++]; else Temp[k++] = subset[j++]; >for (j = 0; j < n; j++) subset[low + j] = Temp[j]; >// end merge >

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

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

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

package com.topjavatutorial; public class ExampleQuickSort < public static void main(String[] args) < // TODO Auto-generated method stub int[] numbers = ; int n = numbers.length; quicksort(numbers, 0, n-1); for (int h = 0; h < n; h++) System.out.print(numbers[h]+ " "); >// Quick sort algorithm public static void quicksort(int[] numbers, int low, int high) < if (low < high) < int dp = partition(numbers, low, high); quicksort(numbers, low, dp-1); quicksort(numbers, dp+1, high); >> // partition numbers[low] to numbers[high] using numbers[low] as the pivot private static int partition(int[] numbers, int low, int high) < int pivot = numbers[low]; int i = low; for (int j = low + 1; j //end for swap(numbers, low, i); return i; > // Exchange list[i] and list[j] values private static void swap(int[] list, int i, int j) < int temp = list[i]; list[i] = list[j]; list[j] = temp; >>

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

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

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

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

package com.topjavatutorial; public class ExampleBubbleSort < public static void main(String[] args) < int[] num = < 3,6,1,7,2,8,10,4,9,5>; int n = num.length; bubbleSort(num); for (int h = 0; h < n; h++) System.out.print(num[h]+ " "); >public static void bubbleSort(int[] numbers) < int n = numbers.length; int temp = 0; for (int i = 0; i < n; i++) < for (int j = 1; j < (n - i); j++) < if (numbers[j - 1] >numbers[j]) < //swap elements temp = numbers[j - 1]; numbers[j - 1] = numbers[j]; numbers[j] = temp; >> > > >

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

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

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

package com.javatutorial; public class ExampleShellsort < public static void main(String[] args) < // TODO Auto-generated method stub int[] num = < 3,6,1,7,2,8,10,4,9,5>; shellSort(num); for (int h : num) System.out.print(h + " "); > public static void shellSort(int[] numbers) < int j; for( int gap = numbers.length / 2; gap >0; gap /= 2 )< for(int i=gap;i= gap && numbers[j - gap] > temp; j -= gap) < numbers[j] = numbers[j - gap]; >numbers[j] = temp; > > > >

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

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

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

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

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

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

package com.topjavatutorial; import java.util.Arrays; public class ExampleBucketSort < public static void main(String[] args) < int[] num = < 3,6,1,7,2,8,10,4,9,5>; int n = num.length; bucketSort(num); for (int h = 0; h < n; h++) System.out.print(num[h]+ " "); >public static int[] bucketSort(int[] arr) < int i, j; int[] bucket = new int[arr.length+1]; Arrays.fill(bucket, 0); for (i = 0; i < arr.length; i++) < bucket[arr[i]]++; >int k=0; for (i = 0; i < bucket.length; i++) < for (j = 0; j> return arr; > >

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

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

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

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

• LSD поразрядная сортировка — сортировка начинается с младшего разряда (LSD), и продолжается до наиболее значимой цифры (MSD);
• MSD поразрядная сортировка — сортировка начинается с наибольшего разряда (MSD), и продолжается до наименьшей значимой цифры (LSD).

package com.javatutorial; import java.util.ArrayList; import java.util.List; public class ExampleRadixSort < public static void main(String[] args) < // TODO Auto-generated method stub int[] num = ; radixsort(num); for (int h : num) System.out.print(h + " "); > public static void radixsort(int[] input) < List[] buckets = new ArrayList[10]; for (int i = 0; i < buckets.length; i++) < buckets[i] = new ArrayList(); > // sort boolean flag = false; int tmp = -1, divisor = 1; while (!flag) < flag = true; // split input between lists for (Integer i : input) < tmp = i / divisor; buckets[tmp % 10].add(i); if (flag && tmp >0) < flag = false; >> // empty lists into input array int a = 0; for (int b = 0; b < 10; b++) < for (Integer i : buckets[b]) < input[a++] = i; >buckets[b].clear(); > // move to next digit divisor *= 10; > > >

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

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

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

package com.javatutorial; public class ExampleCountingSort < public static void main(String[] args) < int[] num = < 3, 6, 1, 7, 2, 8, 10, 4, 9, 5 >; sort(num,num.length); for (int h : num) System.out.print(h + " "); > public static void sort( int[] input,int n) < int min=0,max=0; for (int i = 1; i < n; i++) < if (input[i] >max) max = input[i]; if (input[i] < min) min = input[i]; >int range = max - min + 1; int[] count = new int[range]; //counts frequencies for each element for (int i = 0; i < n; i++) count[input[i] - min]++; // getting positions in final array for (int i = 1; i < range; i++) count[i] += count[i - 1]; //copy to output array, preserving order of inputs with equal keys int j = 0; for (int i = 0; i < range; i++) while (j < count[i]) input[j++] = i + min; >>

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

Оригинальная статья расположена здесь.

Источник

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

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

1. Сортировка массива с помощью Arrays.sort() метод

Arrays class предоставляет несколько статических методов для сортировки массивов:

Он сортирует указанный массив типов примитивов или объектов в порядке возрастания в соответствии с естественным порядком его элементов.

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

Arrays.sort() использует Dual-Pivot Quicksort, который предлагает O(n.log(n)) производительность. Обычно это быстрее, чем традиционный (одноповоротный) Быстрая сортировка реализации.

Он сортирует указанный массив объектов в соответствии с порядком, заданным указанным компаратором. Он требует, чтобы все элементы массива были взаимно сравнимы указанным компаратором, т. е. для любой пары элементов (e1, e2) в массиве, c.compare(e1, e2) не следует бросать ClassCastException .

⮚ Чтобы отсортировать по возрастанию:

⮚ Чтобы отсортировать по убыванию:

Arrays . sort ( arr , Comparator . reverseOrder ( ) ) ; // или используйте `Collections.reverseOrder()`)

Мы также можем написать собственный компаратор, как показано ниже:

Он также предоставляет версию, которая сортирует указанный массив объектов между указанным диапазоном в соответствии с порядком, заданным указанным компаратором:

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

2. Сортировка массива с помощью Arrays.parallelSort() метод

Java 8 также предоставляет Arrays.parallelSort() который использует несколько потоков для сортировки, в отличие от Arrays.sort() который использует только один поток для сортировки элементов. Прототип parallelSort() похоже на sort() .

Это бьет Arrays.sort() когда общее количество элементов превышает определенный порог. Внутри любой массив размером меньше порогового значения сортируется с помощью Arrays.sort() . Порог рассчитывается с учетом параллелизма машины и размера массива. Общий пул ForkJoin используется для выполнения любых параллельных задач.

Следующая программа на Java сравнивает производительность Arrays.parallelSort() с Arrays.sort() на огромном наборе данных из 10 миллионов целых чисел:

Источник