В прошлом уроке мы познакомились с одномерными массивами в Java. Одной из частых задач на работу с массивами является сортировка массива. Сортировкой массива называется процесс упорядочивания элементов массива по возрастанию или по убыванию. В этом уроке мы рассмотрим некоторые способы сортировки и алгоритмы.
Если тема для вас новая, и вы еще не знакомы с алгоритмами сортировки, то наверняка при решении задачи «Отсортировать массив по возрастанию» первое что придет в голову, это перебор, то есть: найти минимальный элемент и поменять его местами с начальным, потом, в оставшейся части массива (кроме первого элемента), найти снова минимальный элемент и поменять его со вторым элементом и т.д. Такой алгоритм называется Сортировка выбором. Рассмотрим его подробнее.
Сортировка выбором (Selection sort) в Java.
Реализация алгоритма Сортировка выбором на Java:
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.
Алгоритм проходит массив от начала и до конца, сравнивая попарно соседние элементы, Если элементы стоят в неправильном порядке, то они меняются местами, таким образом, после первого прохода на конце массива оказывается максимальный элемент (для сортировки по возрастанию). Затем проход массива повторяется, и на предпоследнем месте оказывается другой наибольший после максимального элемент и т.д. В итоге, наименьший элемент постепенно перемещается к началу массива («всплывает» до нужной позиции как пузырёк в воде).
Реализация алгоритма Сортировка пузырьком на 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;
}
}
}
}
Следующие 2 видео наглядно демонстрируют работу алгоритмов сортировки пузырьком и выбором.
Рассмотрим примеры того, как можно воспользоваться выше приведенными алгоритмами.
Для начала создадим массив. Это можно сделать так:
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() сортирует только примитивные типы данных и строки. Как сортировать массив из собственно созданных объектов, будет рассмотрено в следующих уроках, поскольку это требует более углубленных знаний.
Упражнения на тему сортировка массивов в Java:
- Создайте массив из 20 случайных чисел (числа должны быть в диапазоне от 0 до 1000) и отсортируйте массив по убыванию при помощи сортировки пузырьком.
- Создайте массив содержащий марки автомобилей, отсортируйте его сначала по возрастанию, потом по убыванию.
1,2 упражнение http://pastebin.com/ADcGm1F6