| Главная » Статьи » Java » Java Ranger Basic |
День 2/21
| Sorting Algorithms Самых популярных алгоритмов сортировки пять. Три итеративных – пузырьком (Bubble Sort); вставками (Insertion Sort); выборками (Selection sort); и два рекурсивных – быстрая сортировка (Quicksort) и сортировка слиянием (Merge Sort). Пузырьковая сортировка, сортировка выборками и сортировка вставками построены на очень похожих принципах. Их иногда тяжело отличить одну от другой. А также можно их соединить и создать еще одну сортировку, которая тоже будет работать. Первые три сортировки работают примерно n2 времени, а вторые две работают значительно быстрее, n*log2n, где n – это размер массива. К примеру, log2(1024) = 10. Argorithm Average Worst Linear Search N Binary Search log2N Bubble Sort N2 N2 Selection Sort N2 N2 Insertion Sort N2 N2 Quick Sort N∙log2N N2 Merge Sort N∙log2N N∙log2N При поиске, если массив не отсортирован, то единственный вариант – линейный поиск, если отсортирован, то бинарный поиск предпочтительнее. Это оценки для N→∞. Если у нас в массиве 4 элемента, то возможно бинарный поиск будет работать медленнее. Алгоритмы Bubble Sort, Insertion Sort, Selection sort и Quicksort – in-place, они не требуют дополнительного выделения памяти, им нужно только память для счетчиков циклов и временной переменной. А Merge Sort – out-of-place алгоритм, он требует столько же памяти, сколько ему дали сортировать элементов. В следующей теме мы рассмотрим: Primitive Types Источник: http://becomejavasenior.com/courses/?utm_source=Java+Email+Courses&utm_campaign=aa710df388-JavaRangerBasicIntro&utm_medi | |
| Просмотров: 322 | | |
| Всего комментариев: 0 | |