数据结构学习(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

评论

暂无评论