Методы сортировки


Download 194.81 Kb.
bet9/10
Sana04.10.2022
Hajmi194.81 Kb.
#830160
1   2   3   4   5   6   7   8   9   10
Bog'liq
Продвинутые алгоритмы сортировки. Простые методы сортировки. Сортировать по выбору.
dwg fayl, Тарийх кк-тилинде, Hujjat (8), Hujjat (8), 1-лекция, 2-tema, ГЛОССАРИЙ (2), ГЛОССАРИЙ (2), ГЛОССАРИЙ (2), ГЛОССАРИЙ (2), ГЛОССАРИЙ (2), ГЛОССАРИЙ (2), Cv, Cv, amaliy

Реализация


static void heapify(int[] array, int length, int i) {
int leftChild = 2*i+1;
int rightChild = 2*i+2;
int largest = i;


// если левый дочерний больше родительского
if (leftChild < length && array[leftChild] > array[largest]) {
largest = leftChild;
}


// если правый дочерний больше родительского
if (rightChild < length && array[rightChild] > array[largest]) {
largest = rightChild;
}


// если должна произойти замена
if (largest != i) {
int temp = array[i];
array[i] = array[largest];
array[largest] = temp;
heapify(array, length, largest);
}
}

public static void heapSort(int[] array) {


if (array.length == 0) return;


// Строим кучу
int length = array.length;
// проходим от первого без ответвлений к корню
for (int i = length / 2-1; i >= 0; i--)
heapify(array, length, i);


for (int i = length-1; i >= 0; i--) {
int temp = array[0];
array[0] = array[i];
array[i] = temp;


heapify(array, i, 0);
}
}

Временная сложность


Посмотрите на функцию heapify() – кажется, что все делается за O(1), верно? Но нет же: все портит рекурсивный вызов!
Готовы посчитать, сколько вызовов нужно в наихудшем сценарии? В худшем случае рекурсивный вызов дойдет до самой вершины пирамиды прыжками к родителям каждого узла в отношении i/2. Всего потребуется log n прыжков до вершины, значит, сложность равна O(log n).
В связи с циклами for, которые итерируют весь массив, сложность heapSort() равна O(n). Это дает нам суммарную сложность пирамидальной сортировки O(nlog n).

Быстрая сортировка


На этом участнике нашего топа мы закончим разбирать примеры алгоритмов сортировки.
Перед вами очередной алгоритм техники «разделяй и властвуй». Он выбирает один элемент массива в качестве стержня и сортирует остальные элементы вокруг (меньшие элементы налево, большие направо).
Так соблюдается правильная позиция самого «стержня». Затем алгоритм рекурсивно повторяет сортировку для правой и левой частей.

Download 194.81 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   10




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2022
ma'muriyatiga murojaat qiling