Microsoft Word кл программирование на Java 2020 Зорина docx
Полиморфизм при программировании сортировок
жүктеу/скачать 3,23 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Сортировка вставками.
| Полиморфизм при программировании сортировок.
Напомним, что класс, который реализует интерфейс Comparable определяет метод compareTo() , чтобы определить относительный порядок своих объектов. Мы можем использовать полиморфизм, чтобы разработать обобщенную сортировку для любого набора Comparable объектов. Метод сортировки принимает в качестве параметра массив Comparable объектов. Таким образом, один метод может быть использован для сортировки любых объектов, например, People (людей), Books (книг), или любой каких-либо других объектов. Сортировка вставками. Работа метода сортировки: – выбрать любой элемент и вставить его в надлежащее место в отсортированный подсписок; – повторять, до тех пор, пока все элементы не будут вставлены. 68 Более детально: – рассматриваем первый элемент списка как отсортированный подсписок (то есть первый элемент списка); – вставим второй элемент в отсортированный подсписок, сдвигая первый элемент по мере необходимости, чтобы освободить место для вставки нового элемента; – вставим третий элемент в отсортированный подсписок (из двух элементов), сдвигая элементы по мере необходимости; – повторяем до тех пор, пока все значения не будут вставлены на свои соответствующие позиции. // вставками public static void insertionSort (Comparable[] list) { for (int index = 1; index < list.length; index++) { Comparable key = list[index]; int position = index; // Shift larger values to the right while (position > 0 && key.compareTo(list[position-1]) < 0) { list[position] = list[position-1]; position--; } list[position] = key; } } } Пример сортировки вставками на рисунке 5.5: Рисунок 5.5 – Алгоритм сортировки вставками |