Microsoft Word кл программирование на Java 2020 Зорина docx



Pdf көрінісі
бет35/65
Дата17.10.2023
өлшемі3,23 Mb.
#117230
түріРеферат
1   ...   31   32   33   34   35   36   37   38   ...   65
Байланысты:
Лекции

Сравнение сортировок. 
Алгоритмы сортировки выбора и вставки аналогичны по эффективности. Они 
оба имеют внешние циклы, которые сканируют все элементы и внутренние циклы, 
которые сравнивают значение внешнего цикла почти со всеми значениями в списке. 
Приблизительно n2 число сравнений будут сделаны для сортировки списка 
размера n. Поэтому мы говорим, что эти виды сортировок имеют порядок n2. Другие 
виды сортировок являются более эффективными: порядок n log2 n.
Алгоритмы поиска в Java программах 
Поиск является процессом нахождения целевого элемента в пределах группы 
элементов, которая называется пул поиск. Целевой или искомый элемент может 
находится в поисковом пуле, а может там отсутствовать. В любом случае, мы хотим, 
чтобы эффективно выполнять поиск, сводя к минимуму количество сравнений. 
Давайте рассмотрим поиск на двух классических подходах поиска: линейный 
поиск и бинарный поиск. Точно так же, как мы это делали с сортировкой, мы будем 
осуществлять поиск с полиморфными параметрами 
Comparable

Алгоритм линейного поиска. 
Линейный или последовательный поиск начинается на с одного конца списка 
просматриваемых элементов, и все элементы по очереди проверяется на искомый 
элемент. Поиск заканчивается в случае, если найден искомый элемент или достигаем 
конца списка. 
Алгоритм бинарного поиска. 
Бинарный (двоичный) поиск принимает список элементов и помещает их в 
отсортированный пул поиска. Это исключает большую часть поискового пула с 
одним сравнением. Двоичное первый исследует средний элемент списка - если она 
соответствует цели, поиск окончен. Если этого не произойдет, только половина из 
оставшихся элементов нужно искать. Так как они сортируются, цель может быть 
только в одной половине другой. 
Процесс продолжается путем сравнения среднего элемента с оставшимися 
кандидатами на сравнение. Каждое сравнение исключает приблизительно половину 
оставшихся данных. В конце концов, либо искомая цель найдена, или данные для 


70 
поиска исчерпаны. 
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 Framework Collection 
Класс 
ArrayList

Достарыңызбен бөлісу:
1   ...   31   32   33   34   35   36   37   38   ...   65




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет