СОРТИРОВКА ПЕРЕБОРОМ (SELECTION SORT).
Если тема для вас новая, и вы еще не знакомы с алгоритмами сортировки, то наверняка при решении задачи «Отсортировать массив по возрастанию» первое что придет в голову, это перебор, то есть: найти минимальный элемент и поменять его местами с начальным, потом, в оставшейся части массива (кроме первого элемента), найти снова минимальный элемент и поменять его со вторым элементом и т.д. Такой алгоритм называется Сортировка выбором. Рассмотрим его подробнее.
public static void selectionSort(int[] arr){ /*По очереди будем просматривать все подмножества элементов массива (0 - последний, 1-последний, 2-последний,...)*/ for (int i = 0; i < arr.length; i++) { /*Предполагаем, что первый элемент (в каждом подмножестве элементов) является минимальным */ int min = arr[i]; int min_i = i; /*В оставшейся части подмножества ищем элемент, который меньше предположенного минимума*/ for (int j = i+1; j < arr.length; j++) { //Если находим, запоминаем его индекс if (arr[j] < min) { min = arr[j]; min_i = j; } } /*Если нашелся элемент, меньший, чем на текущей позиции, меняем их местами*/ if (i != min_i) { int tmp = arr[i]; arr[i] = arr[min_i]; arr[min_i] = tmp; } } }
СОРТИРОВКА МЕТОДОМ ПУЗЫРЬКА (BUBBLE SORT).
Алгоритм проходит массив от начала и до конца, сравнивая попарно соседние элементы, Если элементы стоят в неправильном порядке, то они меняются местами, таким образом, после первого прохода на конце массива оказывается максимальный элемент (для сортировки по возрастанию). Затем проход массива повторяется, и на предпоследнем месте оказывается другой наибольший после максимального элемент и т.д. В итоге, наименьший элемент постепенно перемещается к началу массива («всплывает» до нужной позиции как пузырёк в воде).
Реализация алгоритма Сортировка пузырьком на Java (по возрастанию):
public static void bubbleSort(int[] arr){ /*Внешний цикл каждый раз сокращает фрагмент массива, так как внутренний цикл каждый раз ставит в конец фрагмента максимальный элемент*/ for(int i = arr.length-1 ; i > 0 ; i--){ for(int j = 0 ; j < i ; j++){ /*Сравниваем элементы попарно, если они имеют неправильный порядок, то меняем местами if( arr[j] > arr[j+1] ){ int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } } }
ПРИМЕРЫ.
Рассмотрим примеры того, как можно воспользоваться выше приведенными алгоритмами.
Для начала создадим массив. Это можно сделать так:
int arr[] ={62, 84, 32, 5, 0, 14, 52, 82, 58, 71};
Или мы можем создать массив случайных чисел:
int arr[] = new int[10]; for(int i = 0; i < arr.length; i++) { //элементу массива присваивается случайное число от 0 до 99 arr[i] = (int)(Math.random() * 100); System.out.print(arr[i] + " "); }
Затем воспользуемся вышеприведёнными алгоритмами сортировки:
System.out.print("\n"); bubbleSort(arr); for(int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); }
или
System.out.print("\n"); selectionSort(arr); for(int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); }
Важно понимать, что сортировки выбором и пузырьком являются простыми, но неэффективными для больших массивов. Эти алгоритмы являются скорее учебными и практически не применяются в жизни. Вместо них используются более эффективные алгоритмы. Подробнее о разных алгоритмах можно прочитать, например, на википедии.
В наше время нет необходимости самостоятельно реализовывать алгоритмы для сортировки, поскольку все что нам нужно, уже имеется в стандартных библиотеках Java.
СОРТИРОВКА МАССИВА ПРИ ПОМОЩИ МЕТОДА SORT() ИЗ КЛАССА ARRAYS.
Метод sort() из класса Arrays использует усовершенствованный алгоритм Быстрой сортировки (Quicksort), который эффективен в большинстве случаев. Для того чтобы отсортировать массив, необходимо написать всего одну строку.
Arrays.sort(arr);// где arr это имя массива
Примечание: в начале файла предварительно нужно подключить библиотеку java.util.
import java.util.*;
СОРТИРОВКА МАСССИВА ЦЕЛЫХ ЧИСЕЛ ПО ВОЗРАСТАНИЮ.
//Создаем массив случайных чисел int arr[] = new int[10]; for(int i = 0; i < arr.length; i++) { arr[i] = (int)(Math.random() * 100); System.out.print(arr[i] + " "); } System.out.print("\nSorted: \n"); //Сортируем массив Arrays.sort(arr); //Выводим отсортированный массив на консоль. for(int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); }
СОРТИРОВКА МАССИВА ЦЕЛЫХ ЧИСЕЛ ПО УБЫВАНИЮ.
//Создаем массив случайных чисел Integer arr[] = new Integer[10]; for(int i = 0; i < arr.length; i++) { arr[i] = (int)(Math.random() * 100); System.out.print(arr[i] + " "); } System.out.print("\nSorted: \n"); //Сортируем массив Arrays.sort(arr, Collections.reverseOrder()); //Выводим отсортированный массив на консоль. for(int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); }
Обратите внимание, что при сортировке массива в обратном порядке (по убыванию) нужно использовать тип Integer[] вместо примитивного типа int[].
СОРТИРОВКА МАССИВА СТРОК В JAVA.
String[] names = new String[] {"Roman","Anna", "Petr", "Maria"}; Arrays.sort(names); for(int i = 0; i < names.length; i++) { System.out.print(names[i] + " "); }
В этом примере массив имен сортируется в порядке от А до Я. Для того чтобы отсортировать массив в обратном порядке, необходимо в методе sort() указать Collections.reverseOrder().
Arrays.sort(names, Collections.reverseOrder());
К сожалению, по умолчанию метод sort() сортирует только примитивные типы данных и строки.
Скопировано отсюда.
Leave A Comment