Сортировка
Следующие три слайда резюмируют все, что мы обсуждали при использовании массива.
Здесь объявляется массив, затем он инициализируется в конструкторе класса.
И затем в методе setScore инициализируются элементы массива.
Метод getScore возвращает элемент массива по его индексу.
А метод aveSore возвращает среднее элементов массива.
Здесь методы возвращают индекс наибольшего элемента в массиве и переставляют два элемента массива.
Заметьте, что этот метод находит позицию максимального элемента, а не само максимальное значение.
Мы также обсуждали в деталях как переставить два элемента в массиве и механизм передачи ссылочной переменной массива в другой метод.
Теперь давайте соберем все это вместе и разработаем важную операцию для работы с массивами, которая называется сортировкой.
Сортировка – это процесс расположения элементов списка в определенном порядке, например, в порядке убывания или возрастания, используя числовой или алфавитный порядок.
Множество приложений требует сортировки, например, упорядочивание группы студентов по их имена или оценкам, упорядочивание списка событий в хронологическом порядке для облегчения поиска информации.
Например, в словарях было бы тяжело искать значение слова, если бы слова не были бы упорядочены в алфавитном порядке.
Или смотреть телефонные номера в списке контактов гораздо проще, если они упорядочены.
Или показ списка веб страниц на основе их популярности, который вы видите каждый день в поиске Google.
Сортировка – это наиболее изучаемая область в компьютерной науке.
Существует много алгоритмов сортировки, но я здесь только дам вам идею как сортировка может быть выполнена и простой алгоритм для понимания.
Алгоритм сортировки, который мы будем рассматривать, называется выборочной сортировкой.
Идея выборочной сортировки простая и следует способу, которым многие из нас выполняют сортировку.
Предположим, что мы сортируем элементы в возрастающем порядке от небольших элементов к большим элементам.
При этом выборочная сортировка разделит сортируемый массив на две части, отсортированную часть и несортированную часть.
Первоначально весь массив считается несортированным.
Затем вы выполняете сортировку, периодически находя больший элемент в не отсортированной части массива, и помещаете его в конец не отсортированной части массива до тех пор, пока весь массив не отсортируется.
Для описания алгоритма в арифметической форме, первый шаг, это установить весь массив как не отсортированный.
Следующий шаг, это итеративный процесс, когда сначала находится больший элемент в не отсортированной части, а затем найденный элемент переставляется с последним элементом не отсортированной части массива.
Например, ищем в массиве самый большой элемент 10, и переставим его с последним элементом 5 в необработанной части массива, и эти две части становятся разными.
Теперь найдем самый большой элемент 9 в необработанной части массива и обменяем его с последним элементом 1 в той же части массива.
Заметим, что этот шаг идентичен предыдущему, за исключением того, что мы не включили в поиск последний элемент, так как мы уже знаем, что он больший.
И эта часть массива уже больше не изменяется.
И с каждой итерацией она становится больше на один отсортированный элемент.
И так весь массив становится отсортированным.
Теперь попробуем реализовать выборочную сортировку в Java программе. Вы можете подумать, что это будет сложная программа.
Вы удивитесь, но это полная реализация выборочной сортировки.
Мы начинаем с объявления переменной maxPos, которая используется для отслеживания большего элемента в не отсортированной части массива.
Мы будем использовать методы maxIndex и swap, которые мы разработали ранее, так как в реализации метода maxIndex вместо возвращения максимального значения, нам нужен метод, возвращающий позицию максимального значения, так что мы сможем сделать перестановку, используя позицию или индекс.
Установим цикл for для повторения шага нахождения большего элемента и его перестановки.
Заметим, что i в цикле for начинается с (scoreArray.length – 1), потому что это последний индекс всего массива, который рассматривается в начале как не отсортированный.
И «i – -» здесь чтобы уменьшать размер не отсортированной части массива на 1.
Заметьте также, что аргумент, который используется при вызове maxIndex, это i + 1, потому что, если вы посмотрите на метод maxIndex, его параметр, это размер массива, в котором метод находит больший элемент.
И размер на 1 больше, чем максимальный индекс.
И для метода swap мы передаем адрес массива в метод.
И второй и третий параметры, это индексы элементов массива для перестановки.
Сортировка изображений
Давайте посмотрим на метод выборочной сортировки, который мы только что обсуждали.
В этом примере мы создали массив оценок, но как я уже говорил, мы также можем создавать массивы различных типов, а не только примитивных типов.
Например, вместо создания массива типа double, как в примере с массивом оценок, мы можем создать массив изображений.
При этом тип массива будет ColorImage.
Здесь пара квадратных скобок указывает, что это массив.
Это объявление создает переменную экземпляра типа массив ColorImage. При этом выделяется память для массива ColorImage с размером NUMBER.
Переменной NUMBER присвоено значение 8.
Затем изображения присваиваются различным элементам массива.
И здесь вы также видите метод selectSort, который похож на предыдущий метод, за исключением длины массива, которая определяется как imageArray.length.
У нас также есть метод swap.
Отличие от предыдущего метода здесь в том, что вместо передачи массива в swap метод, так как массив объявлен как переменная экземпляра, он доступен внутри метода.
Перестановка же здесь похожа на предыдущую реализацию.
Для метода maxIndex я сознательно опустил детали, так что для вас будет хорошим упражнением завершить его.
Теперь посмотрим, что этот класс должен делать.
Если вы создаете экземпляр класса ImageSorter, вы можете видеть, что изображения отображаются на холсте.
И мы пытаемся отсортировать эти изображения по их высоте.
Так что упорядочивание должно начаться с небольшого изображения и закончиться большим изображением.
Вызовом метода moveInPosition, вы можете увидеть изображения, расположенные в возрастающем порядке по их высоте.
