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

Java

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

Сортировка выбором (Selectionsort) в Java

Пример алгоритма Сортировка выбором на Java:

publicstaticvoidselectionSort(int[] arr){
/*По очереди будем просматривать все подмножества
элементов массива (0 — последний, 1-последний,
2-последний,…)*/
for (int i = 0; i <arr.length; i++) {
/*Предполагаем, что первый элемент (в каждом
подмножестве элементов) является минимальным */
intmin = arr[i];
intmin_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) {
inttmp = arr[i];
arr[i] = arr[min_i];
arr[min_i] = tmp;
}
}
}

Сортировка пузырьком (Bubblesort) в Java

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

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

Пример алгоритма Сортировка пузырьком (по возрастанию):

publicstaticvoidbubbleSort(int[] arr){
/*Внешний цикл каждый раз сокращает фрагмент массива,
так как внутренний цикл каждый раз ставит в конец
фрагмента максимальный элемент*/
for(int i = arr.length-1 ; i > 0 ; i—){
for(int j = 0 ; j < i ; j++){
/*Сравниваем элементы попарно,
если они имеют неправильный порядок,
то меняем местами
if( arr[j] >arr[j+1] ){
inttmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}

Для наглядности приведем два видео, которые ярко демонстрируют работу алгоритмов сортировки выбором и пузырьком.

Примеры того, как можно использовать вышеприведенные алгоритмы. Прежде всего, создадим массив:

intarr[] ={62, 84, 32, 5, 0, 14, 52, 82, 58, 71};

Или можно создать массив случайных чисел

intarr[] = newint[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.

importjava.util.*;

Сортировка массива целых чисел по возрастанию:

//Создаем массив случайных чисел
intarr[] = newint[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] + » «);
}

Сортировка массива целых чисел по убыванию:

//Создаем массив случайных чисел
Integerarr[] = newInteger[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 = newString[] {«Roman»,»Anna», «Petr», «Maria»};

Arrays.sort(names);
for(int i = 0; i <names.length; i++) {
System.out.print(names[i] + » «);
}

В данном примере массив имен сортируется от А до Я. Чтобы отсортировать массив в обратном порядке, нужно указать Collections.reverseOrder()в методе sort().

Arrays.sort(names, Collections.reverseOrder());

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

Оцените статью
Образовательный портал WELCOME4U.RU
Добавить комментарий

Adblock
detector