Содержание
- 2. 1.1 Пирамидальная сортировка Пирамидальная сортировка (heap sort (heap − куча)) − алгоритм сортировки, требующий при сортировке
- 3. 1.2 Пирамидальная сортировка В компьютерных науках куча − это специализированная структура данных типа дерево, которая удовлетворяет
- 4. 1.3 Пирамидальная сортировка Сортировка пирамидой использует сортирующее дерево, которое называется пирамидой и является частным случаем кучи.
- 5. 1.4 Пирамидальная сортировка Примеры структур, являющихся пирамидами.
- 6. 1.5 Пирамидальная сортировка Алгоритм построения пирамиды Можно построить пирамиду снизу вверх. 1. Вначале разместим элементы исходного
- 7. 1.6 Пирамидальная сортировка
- 8. 1.7 Пирамидальная сортировка Перемещение элемента из положения Queue[parent] вниз по пирамиде. Если поддеревья ниже Queue[parent] являются
- 9. 1.8 Пирамидальная сортировка
- 10. 1.9 Пирамидальная сортировка Полный алгоритм, использующий процедуру HeapPushDown для создания пирамиды из дерева элементов.
- 11. 1.10 Пирамидальная сортировка Очереди с приоритетом Удаление элемента из очереди с приоритетом Если в качестве очереди
- 12. 1.11 Пирамидальная сортировка Добавление элемента к очереди с приоритетом Поместим новый элемент на свободное место в
- 13. 1.12 Пирамидальная сортировка Анализ пирамид При первоначальном превращении списка в пирамиду осуществляется создание множества пирамид меньшего
- 14. 1.13 Пирамидальная сортировка Время для построения пирамиды Пусть H — высота дерева. Это полное двоичное дерево,
- 15. 1.14 Пирамидальная сортировка Время для удаления максимального элемента Для удаления элемента из очереди с приоритетом, последний
- 16. 1.15 Пирамидальная сортировка Алгоритм пирамидальной сортировки Алгоритм пирамидальной сортировки использует уже описанные алгоритмы для работы с
- 17. 1.16 Пирамидальная сортировка Алгоритм сортировки состоит из двух основных шагов: 1.Выстраиваем элементы массива в виде сортирующего
- 18. 1.17 Пирамидальная сортировка Время выполнения алгоритма пирамидальной сортировки Первоначальное построение пирамиды требует O(N) шагов. После этого
- 19. 1.18 Пирамидальная сортировка
- 20. 1.19 Пирамидальная сортировка Пример. Пирамидальная сортировка (в узлах указаны номера элементов массива).
- 21. 1.20 Пирамидальная сортировка
- 22. 1.21 Пирамидальная сортировка Достоинства и недостатки алгоритма пирамидальной сортировки Достоинства Имеет доказанную оценку худшего случая O(n
- 23. 2.1 Сортировка подсчетом Сортировка подсчетом (counting sort) — специализированный алгоритм, который очень хорошо работает, если элементы
- 24. 2.2 Сортировка подсчетом Алгоритм сортировки подсчетом 1 шаг. Создается массив для подсчета числа элементов, имеющих определенное
- 25. 2.3 Сортировка подсчетом Время работы алгоритма Алгоритм целиком требует порядка O(M)+O(N)+O(N)=O(M+N) шагов. Если M Пример. Если
- 26. 2.4 Сортировка подсчетом
- 27. 2.5 Сортировка подсчетом
- 28. 3.1 Блочная сортировка Блочная сортировка (карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в
- 29. 3.2 Блочная сортировка Алгоритм Алгоритм использует значения элементов для разбиения их на на множество блоков, и
- 30. 3.3 Блочная сортировка Сложность алгоритма Если в списке N элементов, и алгоритм использует N блоков, в
- 31. 3.4 Блочная сортировка Пример. Число блоков (корзин) меньше числа элементов.
- 32. 3.5 Блочная сортировка Пример. Число блоков равно числу элементов
- 33. 3.6 Блочная сортировка Реализовать алгоритм блочной сортировки можно различными способами. Блочная сортировка на основе одномерного массива
- 34. 3.6 Блочная сортировка Блочная сортировка с использованием связанных списков Можно использовать в качестве блоков связанные списки.
- 35. 3.7 Блочная сортировка
- 36. 3.8 Блочная сортировка
- 37. 3.9 Блочная сортировка
- 38. 3.10 Блочная сортировка
- 39. 4.1 Распределяющая сортировка Распределяющая сортировка относится к быстрым алгоритмам, не использующим операции сравнения, с временем выполнения
- 40. 4.2 Распределяющая сортировка Пример Рассмотрим реализацию распределяющей сортировки при Т=2 для списка: B= . J=1. Распределение
- 41. 4.3 Распределяющая сортировка Время выполнения Количество действий, необходимых для сортировки списка из N T-значных чисел, определяется
- 43. Скачать презентацию