数据结构学习(shell排序和归并排序)
文章目录
AppleScript]纯文本查看__复制代码
01
02
03
04
05
06
07
08
09
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
# coding=utf-8[/align]
# shell排序
# 参数alist:被被排序的列表
def shellsort`(alist)`:
gap = len`(alist) / 2`
while gap > 0`:`
for i in range`(gap)`:
shellinsert`(alist, i,` `gap)`
gap = gap / 2
print alist
#根据步长进行插入排序
def shellinsert`(alist, start,` `gap)`:
for i in range`(start` `+` `gap, len(alist), gap):`
temp = alist[i]
position = i
while position >`= gap and alist[position` `-` `gap]` `>` `temp:`
alist[`position]` `=` `alist[position - gap]`
position = position - gap
alist[`position`] = temp
# 归并排序
# 参数alist:被被排序的列表
def mege_sort`(alist)`:
if len`(alist) <=` `1:`
return alist
num = int`(len(alist) / 2`)
leftList = mege_sort`(alist[:num])`
rightList = mege_sort`(alist[num:])`
return mege`(leftList, rightList`)
#将两个列表合并为一个列表进行返回
def mege`(leftList, rightList):`
l = 0
r = 0
result = []
while l < len`(leftList) and r < len(rightList):`
if leftList[l] < rightList[r]`:`
result`.append(leftList[l]`)
l +`= 1`
else`:`
result`.append(rightList[r]`)
r +`= 1`
result = result + leftList[l`:`]
result = result + rightList[r`:`]
return result
alist = [`9,` `8, 9,` `9, 7,` `6, 5,` `4, 3,` `2, 1`]
if __name__ =`= '__main__'`:
# shellsort(alist)
result = mege_sort`(alist)`
print alist
print result
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论