|
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
|
array
=
[
0
,
30
,
20
,
80
,
40
,
50
,
10
,
60
,
70
,
90
]
# 待排序序列
# i = 4-1 或 1
# n = len(array)
total
=
len
(array)
-
1
# 调整为大顶堆,i是指从哪个结点开始调整,n代表待排序元素总数
def
adjust_heap(n,i,array):
#length = len(array)
#print_tree(array)
while
i
*
2
<
=
n:
lchild_index
=
2
*
i
max_child_index
=
lchild_index
if
n > lchild_index
and
array[lchild_index
+
1
] > array[lchild_index]:
max_child_index
=
lchild_index
+
1
if
array[max_child_index] > array[i]:
array[max_child_index],array[i]
=
array[i],array[max_child_index]
i
=
max_child_index
else
:
break
# 选择从哪个结点开始排序
for
i
in
range
(
4
,
0
,
-
1
):
adjust_heap(
len
(array)
-
1
,i,array)
# 选择排序实现
def
sort(total,array):
while
total >
1
:
array[
1
],array[total]
=
array[total],array[
1
]
total
-
=
1
# 特殊情况,当只剩两元素时,直接比较,不用调整
if
total
=
=
2
and
array[
1
] < array[total]:
break
adjust_heap(total,
1
,array)
return
array
sort(total,array)
|
本文转自 撒旦搞时间 51CTO博客，原文链接：http://blog.51cto.com/12074120/1976141，如需转载请自行联系原作者
