TeachMeSkills. Java developer. Lesson 3

1.

<TeachMeSkills/>
Школа программирования
teachmeskills.com

2.

курс
Java разработчик
Занятие 3. Одномерные массивы

3.

Агенда занятия
Что такое массивы
Одномерные массивы
Out of the box классы и методы для работы с массивами
Алгоритмы сортировки массива

4.

Что такое массивы
Одномерные массивы
Out-of-the-box классы и методы для работы с массивами
Алгоритмы сортировки массива
4

5.

Что такое массивы
Массив в java - это конечное именованное множество переменных одного
типа.
Массивы позволяют удобно группировать информацию и получать доступ к
ней.
Массивы могут быть одномерными, двумерными и многомерными.

6.

Что такое массивы
Одномерные массивы
Out-of-the-box классы и методы для работы с массивами
Алгоритмы сортировки массива
6

7.

Одномерные массивы
Если в массиве для обращения к элементам используется только один
порядковый номер, то такой массив называется одномерным.
Одномерный массив можно представить в виде таблицы, в которой
существует только одна строка.

8.

Одномерные массивы.
Объявление массива
Чтобы создать массив, нужно сначала объявить переменную массива
требуемого типа.
Общая форма объявления одномерного массива выглядит следующим
образом:

9.

Одномерные массивы.
Инициализация массива
Инициализация массива - это создание реального объекта для хранения
массива в области памяти Java.
При создании массива без его явного заполнения все его элементы
инициализируется дефолтными значениями (значениями по умолчанию).

10.

Одномерные массивы.
Инициализация с помощью new
Ключевое слово new используется для выделения памяти под массив

11.

Одномерные массивы.
Инициализация с помощью new
Массив может быть объявлен и инициализирован одной строкой

12.

Одномерные массивы.
Индексация элементов массива

13.

Одномерные массивы.
Запись значений в массив
Позиция элемента в массиве называется индексом

14.

Одномерные массивы.
Заполнение массива значениями

15.

Одномерные массивы.
Заполнение массива при инициализации
(Блоки инициализации)

16.

Одномерные массивы.
Размер массива
Размер массива может быть запрошен через его свойство length.

17.

Одномерные массивы.
Инициализация массива с помощью цикла

18.

Одномерные массивы.
Инициализация массива с помощью цикла
Пример:

19.

Одномерные массивы.
Цикл for-each
Форма записи for (инициализация; условие выхода; счетчик) {} часто бывает избыточна и
многословна, поэтому в Java есть более компактная форма записи:

20.

Одномерные массивы.
Цикл for-each

21.

Что такое массивы
Одномерные массивы
Out-of-the-box классы и методы для работы с массивами
Алгоритмы сортировки массива
21

22.

OOTB (out of the box)
классы и методы для работы с массивом
Метод Arrays.toString()
Метод Arrays.toString() возвращает строковое представление одномерного массива,
разделяя элементы запятой.

23.

OOTB (out of the box)
классы и методы для работы с массивом
Arrays.toString()

24.

OOTB (out of the box)
классы и методы для работы с массивом
Метод Arrays.sort()
Метод Arrays.sort() позволяет сортировать элементы массива по возрастанию.

25.

OOTB (out of the box)
классы и методы для работы с массивом
Метод Arrays.sort()

26.

OOTB (out of the box)
классы и методы для работы с массивом
Метод Arrays.binarySearch()
Метод Arrays.binarySearch() возвращает позицию заданного значения.
Если искомый элемент не найден, то возвращается - (position + 1), где position - позиция
элемента где он МОГ БЫ БЫТЬ.
Массив должен быть отсортирован, иначе результат вызова метода будет не определен.

27.

OOTB (out of the box)
классы и методы для работы с массивом
Метод Arrays.binarySearch()

28.

OOTB (out of the box)
классы и методы для работы с массивом
Метод System.arraycopy()
Метод System.arraycopy() осуществляет копирование части массива в другой массив.

29.

OOTB (out of the box)
классы и методы для работы с массивом
Метод System.arraycopy()

30.

Что такое массивы
Одномерные массивы
Out-of-the-box классы и методы для работы с массивами
Алгоритмы сортировки массива
30

31.

Алгоритмы сортировки массива
Понятие сложности алгоритма
Сложность алгоритмов обычно оценивают по времени выполнения или по используемой
памяти. В обоих случаях сложность зависит от размеров входных данных.
При этом точное время мало кого интересует: оно зависит от процессора, типа данных,
языка программирования и множества других параметров.
Важна лишь асимптотическая сложность, т. е. сложность при стремлении размера
входных данных к бесконечности.

32.

Алгоритмы сортировки массива
Основные алгоритмы
Сортировка пузырьком
Сортировка вставками
Сортировка выбором
Сортировка слиянием
Пирамидальная сортировка
Быстрая сортировка

33.

Алгоритмы сортировки массива
Сортировка пузырьком
Алгоритм проходит массив от начала и до конца, сравнивая попарно
соседние элементы.
Если элементы стоят в неправильном порядке, то они меняются местами,
таким образом, после первого прохода на конце массива оказывается
максимальный элемент (для сортировки по возрастанию).
Затем проход массива повторяется, и на предпоследнем месте оказывается
другой наибольший после максимального элемент и т.д.
В итоге, наименьший элемент постепенно перемещается к началу массива
(«всплывает» до нужной позиции как пузырёк в воде).

34.

Алгоритмы сортировки массива
Быстрая сортировка
Пошаговое описание алгоритма сортировки:
1.Выбираем опорный элемент из массива. Как правило, это средний элемент.
2.Делим массив на 2 подмассива. Элементы, которые меньше опорного, и
элементы, которые больше опорного.
3.Рекурсивно применяем сортировку к обоим подмассивам.
В результате массивы будут делиться до тех пор, пока не останется один
элемент.
Большинство готовых библиотек и методов по сортировке используют quick
sort алгоритм как основу.

35.

Алгоритмы сортировки массива
Быстрая сортировка
Важные детали:
алгоритм рекурсивный
сортирует некоторую часть массива с заданными индексами (включительно)
на произвольном массиве нет большой разницы какой элемент выбирать опорным

36.

Полезные ссылки
Одномерные массивы
Длина массива
Массивы. For и For-each
Метод Arrays.toString()
Метод Arrays.sort()
Метод Arrays.binarySearch()

37.

Полезные ссылки
Метод System.arraycopy()
Топ 6 алгоритмов сортировки
Немного о сложности алгоритмов
Шилдт. Стр 172 - 178

38.

Q&A
Ваши вопросы

39.

Спасибо
<TeachMeSkills/>