forked from nxexox/aist
-
Notifications
You must be signed in to change notification settings - Fork 0
/
heap_sort.py
46 lines (34 loc) · 1.31 KB
/
heap_sort.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#!/usr/bin/python
# coding: utf8
def heap_sort(_list):
"""
Пирамидальная сортировка. Строим CБД слева направо.
По закону: a[i] >= a{2*i + 1] and a[i] >= a[2*i + 2]. Иначе говоря, это КУЧА.
2 этапа. Постороение пирамиды, Сортировка
:params _list: Массив для сортировки.
:type _list: list
:return: Отсортированный массив.
:rtype: list
"""
length = len(_list)
# Меняем местами.
def swap(pi, ci):
if _list[pi] < _list[ci]:
_list[pi], _list[ci] = _list[ci], _list[pi]
# Просеивание через КУЧУ.
def sift(index, unsorted):
while index * 2 + 2 < unsorted:
gtci = max(_list[index * 2 + 1], _list[index * 2 + 2])
swap(index, gtci)
index = gtci
# Строим пирамиду. Правая часть дерева n/2 - 1
for i in range(int((length / 2)) - 1, -1, -1):
sift(i, length)
# sort
for i in range(length - 1, 0, -1):
swap(i, 0)
sift(0, i)
return _list
if __name__ == "__main__":
test_list = [12, 68, 213, 1, 59, 394, 43, 12, 645, 324, 98, 999, 998]
print(heap_sort(test_list))