Изучение языка программирования Python



Pdf көрінісі
бет13/14
Дата04.03.2023
өлшемі1,23 Mb.
#171016
1   ...   6   7   8   9   10   11   12   13   14
Байланысты:
python

3.
 
Алгоритм быстрой сортировки 
def partition(alist, left, right):
#Середина 
x = alist[left + (right - left) // 2] 
i = left 
j = right 
while i < j: 
print(alist) 
while alist[j] > x and not j < left: 
j -= 1 
while alist[i] right: 
i += 1 
if i < j: 
#Меняем местами переменные 
alist[i],alist[j] = alist[j],alist[i] 
j -= 1 
return j 
def quickSort(alist, left, right): 
if right > left: 
q = partition(alist, left,right) 
quickSort(alist,left,q) 
quickSort(alist, q+1, right)
4.
 
Бинарный поиск 
def binarySearch(lst, key):
l = 0 
#начало
r = len(lst) 
#конец
while l < r - 1: 
m = l + (r - l) // 2 
#Середина списка
if lst[m] > key: 
r = m 
else: 
l = m 
if lst[l] == key: 
return str(lst[l]) + "\nНайдено" 
else: 
return("Не найдено")
Бинарное дерево поиска 
Сначала определим класс дерева –
TreeItem
, встречаемый ранее и 
добавим поле 
key
(значение узла). 
class TreeItem: 
def __init__(self, key = None): 
self.right = None 


28
self.left = None 
self.key = key 
Зададим начальные значения узлов. 
root = TreeItem(200) 
root.left=TreeItem(42) 
root.right=TreeItem(420) 
Опишем функцию 
insertItem
добавления элемента в дерево. Это 
сделать можно, только найдя его место. Для этого нам потребуется функция 
поиска элемента в дереве. Для удобства добавим комментарий о том, справа 
или слева от какого узла помещен новый элемент. 
def insertItem(inp): 
global root 
if root: 
curItem = root 
#Поиск нужного места и вставка нового элемента 
while not curItem == None and not curItem.key == inp: 
if curItem.key > inp: 
if curItem.left == None or curItem.left.key == 
None: 
print("Помещаем слева от 
"+str(curItem.key)) 
curItem.left = TreeItem(inp) 
break 
else: 
#Переход влево 
curItem = curItem.left 
elif curItem.right == None: 
print("Помещаем справа от " + str(curItem.key)) 
curItem.right = TreeItem(inp) 
break 
else: 
if curItem.right == None or curItem.right.key 
== None: 
print("Помещаем справа от " + 
str(curItem.key)) 
curItem.right = TreeItem(inp) 
break 
else: 
#Переход вправо 
curItem = curItem.right 
else: 
root = TreeItem(inp) 


29


Достарыңызбен бөлісу:
1   ...   6   7   8   9   10   11   12   13   14




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

    Басты бет