Сызықтық, ретті іздеу (Линейный, последовательный)


Реализация быстрой сортировки 1



бет4/4
Дата26.07.2023
өлшемі0,89 Mb.
#104796
1   2   3   4
Байланысты:
Алгоритм 5

Реализация быстрой сортировки 1







Біріктіру сұрыптауы (Сортировка слиянием, merge sort)


Сортировка слиянием также следует стратегии «разделяй и властвуй». Разделяем исходный массив на два равных подмассива. Повторяем сортировку слиянием для этих двух подмассивов и объединяем обратно.

Цикл деления повторяется, пока не останется по одному элементу в массиве. Затем объединяем, пока не образуем полный список.


Алгоритм сортировки состоит из четырех этапов:

  1. Найти середину массива.

  2. Сортировать массив от начала до середины.

  3. Сортировать массив от середины до конца.

  4. Объединить массив.

Для объединения напишем отдельную функцию merge().


Алгоритм объединения массивов:

  1. Циклично проходим по двум массивам..

  2. В объединяемый ставим тот элемент, что меньше.

  3. Двигаемся дальше, пока не дойдем до конца обоих массивов.

Сложность в любом случае: O(n*logn).



Пирамидальная сортировка (HeapSort)






Достарыңызбен бөлісу:
1   2   3   4




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

    Басты бет