Лексикографический порядок чисел 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. Сортировать в лексикографическом порядке

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

результат:

[1, 2, 1, 2]
[1, 3, 1, 2]
[1, 3, 2, 2]

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

Мы также можем сортировать отдельные списки в порядке возрастания с помощью компаратора. Следующий код использует Stream API для сортировки каждого списка с помощью Comparator.naturalOrder() comparator.

результат:

[1, 2, 3]
[1, 1, 2, 2]
[1, 1, 3]

3. Сортировка в лексикографическом и возрастающем порядке

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

результат:

[1, 1, 1]
[1, 1, 2, 2]
[1, 1, 2, 3]
[1, 2, 2, 3]
[1, 2]
[2, 3]

Это все о сортировке списка списков в Java.

Средний рейтинг 5 /5. Подсчет голосов: 4

Голосов пока нет! Будьте первым, кто оценит этот пост.

Сожалеем, что этот пост не оказался для вас полезным!

Расскажите, как мы можем улучшить этот пост?

Спасибо за чтение.

Пожалуйста, используйте наш онлайн-компилятор размещать код в комментариях, используя C, C++, Java, Python, JavaScript, C#, PHP и многие другие популярные языки программирования.

Как мы? Порекомендуйте нас своим друзьям и помогите нам расти. Удачного кодирования 🙂

Этот веб-сайт использует файлы cookie. Используя этот сайт, вы соглашаетесь с использованием файлов cookie, нашей политикой, условиями авторского права и другими условиями. Читайте наши Политика конфиденциальности. Понятно

Источник