Материал: 4 - Полиморфизм
Более детально:
•рассматриваем первый элемент списка как отсортированный подсписок (то есть первый элемент списка)
•вставим второй элемент в отсортированный подсписок, сдвигая первый элемент по мере необходимости, чтобы освободить место для вставки нового элемента
•вставим третий элемент в отсортированный подсписок (из двух элементов), сдвигая элементы по мере необходимости
•повторяем до тех пор, пока все значения не будут вставлены на свои соответствующие позиции
Один класс - два метода сортировки
public class Sorting { //выбором
public static void selectionSort (Comparable[] list) { int min;
Comparable temp;
for (int index = 0; index < list.length-1; index++)
{
min = index;
for (int scan = index+1; scan < list.length; scan++) if (list[scan].compareTo(list[min]) < 0)
min = scan; temp = list[min];
list[min] = list[index]; list[index] = temp;
}
}
//вставками
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;
}
}
}
public class DemoPhoneList{
public static void main (String[] args) { Contact[] friends = new Contact[8];
friends[0] = new Contact ("John", "Smith", "610-555-7384"); friends[1] = new Contact ("Sarah", "Barnes", "215-555-
3827");
friends[2] = new Contact ("Mark", "Riley", "733-555-2969"); friends[3] = new Contact ("Laura", "Getz", "663-555-3984"); friends[4] = new Contact ("Larry", "Smith", "464-555-
3489");
friends[5] = new Contact ("Frank", "Phelps", "322-555- 2284");
friends[6] = new Contact ("Mario", "Guzman", "804-555- 9066");
friends[7] = new Contact ("Marsha", "Grant", "243-555- 2837");
Sorting.selectionSort(friends);
for (Contact friend : friends) System.out.println (friend);
}
}
Сравнение сортировок
Алгоритмы сортировки выбора и вставки аналогичны по эффективности. Они оба имеют внешние циклы, которые сканируют все элементы и внутренние циклы, которые сравнивают значение внешнего цикла почти со всеми значениями в списке. Приблизительно n2 число сравнений будут сделаны для сортировки списка размера n. Поэтому мы говорим, что эти виды сортировок имеют порядок n2. Другие виды сортировок являются более эффективными: порядок n log2 n.
Алгоритмы поиска в Java программах
Поиск является процессом нахождения целевого элемента в пределах группы элементов, которая называется называется пул поиск. Целевой или искомый элемент может находится в поисковом пуле, а может там
отсутствовать. В любом случае, мы хотим, чтобы эффективно выполнять поиск, сводя к минимуму количество сравнений. Давайте рассмотрим поиск на двух классических подходах поиска: линейный поиск и бинарный поиск. Точно так же как мы это делали с сортировкой, мы будем осуществлять поиск с полиморфными параметрами Comparable.
Алгоритм линейного поиска
Линейный или последовательный поиск начинается на с одного конца списка просматриваемых элементов, и все элементы по очереди проверяется на искомый элемент. Поиск заканчивается в случае, если найден искомый элемент или достигаем конца списка.
Алгоритм бинарного поиска
Бинарный (Двоичный) поиск принимает список элементов и помещает их в отсортированный пул поиска. Это исключает большую часть поискового пула с одним сравнением. Двоичное первый исследует средний элемент списка - если она соответствует цели, поиск окончен. Если этого не произойдет, только половина из оставшихся элементов нужно искать. Так как они сортируются, цель может быть только в одной половине другой.
Бинарный поиск
Процесс продолжается путем сравнения среднего элемента с оставшимися кандидатами на сравнение. Каждое сравнение исключает приблизительно половину оставшихся данных. В конце концов, либо искомая цель найдена, или данные для поиска исчерпаны.
Два метода в одном классе
public class Searching{ // линейный
public static Comparable linearSearch (Comparable[] list,Comparable target) {
int index = 0; boolean found = false;
while (!found && index < list.length) { if (list[index].compareTo(target)==0)
found = true; else
index++;
}
if (found)
return list[index]; else
return null;
}
//Двоичный поиск
public static Comparable binarySearch (Comparable[] list,Comparable target) {
int min=0, max=list.length-1, mid=0; boolean found = false;
while (!found && min <= max) { mid = (min+max) / 2;
if (list[mid].compareTo(target)==0) found = true;
else
if (target.compareTo(list[mid]) < 0) max = mid-1;
else
min = mid+1; }
if (found) return list[mid]; else return null;}}
public class PhoneList2 {
public static void main (String[] args) { Contact test, found;
Contact[] friends = new Contact[8];
friends[0] = new Contact ("John", "Smith", "610-555-7384"); friends[1] = new Contact ("Sarah", "Barnes", "215-555-
3827");
friends[2] = new Contact ("Mark", "Riley", "733-555-2969"); friends[3] = new Contact ("Laura", "Getz", "663-555-3984"); friends[4] = new Contact ("Larry", "Smith", "464-555-
3489");
friends[5] = new Contact ("Frank", "Phelps", "322-555- 2284");
friends[6] = new Contact ("Mario", "Guzman", "804-555- 9066");
friends[7] = new Contact ("Marsha", "Grant", "243-555- 2837");
test = new Contact ("Frank", "Phelps", "");
found = (Contact) Searching.linearSearch(friends, test);
if (found != null)
System.out.println ("Found: " + found); else
System.out.println ("The contact was not found."); System.out.println (); Sorting.selectionSort(friends);
test = new Contact ("Mario", "Guzman", "");
found = (Contact) Searching.binarySearch(friends, test); if (found != null)
System.out.println ("Found: " + found); else
System.out.println ("The contact was not found.");
} }
Строки в Java
•Класс String
•StringBuffer
•StringBuilder
Особенности использования строк в Java
Java предоставляет специальный механизм для хранения последовательностей символьных литералов (строк), так называемый общий пул строк.
Если две последовательности литералов (строки) имеют одинаковое содержание, то они разделяют общее пространство для хранения внутри общего пула.
Такой подход принят для того чтобы сохранить место для хранения часто используемых строк.
С другой стороны, объекты типа String (строки), созданные с помощью оператора new и конструктора хранятся в куче.
Коротко о классе String
ВJava строки представляют собой неизменяемую последовательность символов Unicode.
Вотличие от представления в C / C ++, где строка является просто массивом типа char, любая Java, строка является объектом класса java.lang.String.
Однако Java строка, представляет собой в отличие от других используемых классов особый класс, который обладает довольно специфичными характеристиками.
Строка является неизменяемой, то есть, символьной константой. Это значит, что ее содержание не может быть изменено после ее (строки как объекта) создания. Например, метод toUpperCase () – преобразования к верхнему регистру создает и возвращает новую строку вместо изменения содержания существующей строки.