6 апреля 2014 
Мария (admin)
В прошлом уроке мы познакомились с одномерными массивами в 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) и отсортируйте массив по убыванию при помощи сортировки пузырьком.
- Создайте массив содержащий марки автомобилей, отсортируйте его сначала по возрастанию, потом по убыванию.
Категория: 
Не получается запустить ваш пример на сортировку массива по убыванию. Ругается на третью строку: «arr[i] = (int)(Math.random() * 100);». Пишет, что несоответствие типов.
не знаю.. у меня запускается без проблем
Создал новый класс, скопировал туда один в один код отсюда. Добавил только в начале два импорта, без них отказывался запускаться. Конечный результат здесь: http://pastebin.com/q80uxEth. Там возле строки написана ошибка.
не могу воспроизвести вашу ошибку. В чем работаете? в эклипсе?
Да. Ставил по ссылке отсюда, из 3-го урока. Все прочие программы и примеры работают нормально.
Добрый день!
Мария, если я правильно понял, случайные числа функция Math.random() делает в десятых (от 0 до 1). Поэтому мы умножаем это на 100, чтобы получить от 0 до 100. В Вашем задании необходимо получить случайные числа от 0 до 1000. Как это сделать? Ведь если Math.random() умножить на 1000, тогда числа будут от 100 до 1000.
Подскажите, плиз.
нет, если умножить на 1000, то будут от 0 до 1000
Мария, а подскажите, пожалуйста..
Я читаю Ваши уроки и книгу «Шилдт. Java: полное руководство». Что мне в ней не нравится — отсутствие заданий или упражнений! У Вас, после пройденного урока, есть упражнения. Их делаешь, материал откладывается.. А там фактически прочитал, все понятно, но потом ничего не вспомнишь..
Так вот) Подскажите, где можно найти подобные Вашим упражнения? Или не могли бы посоветовать книгу с упражнениями после глав?
Заранее спасибо)
Соглашусь с вами. Дело в том, что Шилдт это справчник, поэтому он не совсем подходит в качестве учебного курса. Упражнения после глав есть в учебнике Java. Промышленное программирование И.Н. Блинов, В.С. Романчик. Но там, на мой взгляд, не очень последовательно излагается материал. Еще можете погуглить по каждой теме что-то вроде «Java массивы задачи упражнения»
Если время появится, обязательно продолжайте. Очень доступно излагаете материал.
Здравствуйте!
Очень крутые уроки и доступные для понимания. Скажите, а когда новый урок будет?
Здравствуйте, пока не могу сказать. со временем напряженка