Двойно хеширане:
При двойното хеширане, използваме втора хеш-функция h2(k) и търсим следващата свободна позиция по формулата: h′(k,i)=(h(k)+i⋅h2(k))mod m, където h(k) е първата хеш стойност, h2(k) е втората хеш стойност, i е броят на пробваните позиции, и m е размерът на таблицата.
Алгоритми за сортиране - сортиране чрез сливане(четно и нечетно сливане), сортиране чрез разпределяне. Примери.
Сортиране чрез сливане (Merge Sort):
Основен принцип:
Процедура на сортиране чрез сливане:
Разделяне на списъка на две половини.
Рекурсивно сортиране на всяка от половините.
Сливане на сортираните половини обратно заедно.
Сортиране чрез разпределяне (Quick Sort):
Основен принцип:
Сортирането чрез разпределяне е ефективен алгоритъм, който използва принципа на "разделяй и владей". Този алгоритъм избира елемент (пивот) от масива и подрежда елементите по-малки от пивота вляво, а по-големите - вдясно. След това се рекурсивно прилага върху двете подмасива.
Процедура на сортиране чрез разпределяне:
Избиране на пивот от масива.
Разпределяне на елементите на два подмасива - по-малки и по-големи от пивота.
Рекурсивно сортиране на подмасивите.
Сподели с приятели: |