Microsoft Word кл программирование на Java 2020 Зорина docx
жүктеу/скачать 3,23 Mb. Pdf көрінісі
|
Лекции
- Бұл бет үшін навигация:
- Алгоритм линейного поиска.
- Алгоритм бинарного поиска.
| Сравнение сортировок.
Алгоритмы сортировки выбора и вставки аналогичны по эффективности. Они оба имеют внешние циклы, которые сканируют все элементы и внутренние циклы, которые сравнивают значение внешнего цикла почти со всеми значениями в списке. Приблизительно 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 жүктеу/скачать 3,23 Mb. Достарыңызбен бөлісу:
|