В прошлом уроке мы познакомились с одномерными массивами в 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) и отсортируйте массив по убыванию при помощи сортировки пузырьком.
- Создайте массив содержащий марки автомобилей, отсортируйте его сначала по возрастанию, потом по убыванию.
Здравствуйте, Мария! Спасибо огромное за проделанный труд. С нетерпением жду дальнейших уроков. Я понимаю, что времени часто не хватает, но все же выскажу пожелание. Не могли бы Вы хотя бы выложить план уроков, структуру, название последующих уроков, ну в общем что-то в этом духе. Это поможет, тем кто остановился на данном последнем уроке пойти далее. Я понимаю, что ответ на свой вопрос могу найти самостоятельно, но все же наверняка у Вас определенный педагогический подход, и есть какая-то стратегия изучения. Если это не противоречит Вашему проекту, буду весьма признателен) И не только я)
Заранее спасибо!
Здравствуйте. Ради интереса пытался сортировать массивы с помощью Arrays. При сортировке по убыванию, ругается на 11 строку, а именно на тип инт http://pastebin.com/7sqrQ92u . Хотя писал по Вашему примеру.
С нетерпением жду следующих уроков. Спасибо!
Здравствуйте, в комментариях выше уже встречалась такая проблема, но в чем причина я не знаю. У меня ваш код компилируется и запускается.
Попробуйте так написать http://pastebin.com/pwR5M4bu может быть поможет.
Или так
arr[i] = Math.round((float)Math.random() * 1001);
Если будет работать — напишите, я исправлю в уроке, еще напишите java какой версии у вас установлена.
Здравствуйте!
Начал читать рекомендованную книгу (с начала), пока много теории, чтобы не скучать, решил поломать голову над сортированием многомерного массива. Сначала думал, как это реализовать, а потом потратил некоторое время реализовывая… Нашел в инете, как оформляется многомерный массив.
Как оказалось, очень важно ежедневно использовать полученные знания, ибо пришлось заглядывать в урок по сортировке одномерного массива, потому как по памяти воссоздать не сумел. А еще, важна внимательность к деталям, в моем случае, к именам массивов, т.к. некоторое время потратил на поиск, почему же простой и осмысленный код не работает, пока как-то случайно не заметил, что в имени второго массива не хватает циферки.
В любом случае, вот что получилось:
http://pastebin.com/DrQ0BWbX
Да, нужно постоянно практиковаться, чтобы в голове отложилось и не пришлось подглядывать. Это не только в программированиии так, все неиспользуемые знания со временем забываются (кроме может езды на велосипеде))) Да и в подглядывании ничего стршного не вижу, все помнить нельзя, важно знать, где можно посмотреть и потом суметь этим воспользоваться. А переменные лучше называть осмысленно, а не просто буквами, чтобы потом не было путаницы.
Здравствуйте! Вы бы не могли сравнить предложенную Вами книгу, с Философией Java Брюса Эккеля. Какая предпочтительнее?
Обе хорошие, читайте то, что вам кажется понятнее
Очень хорошие и понятные уроки, присоединяюсь к обучению. Огромное спасибо автору!