CoCalc -- example02.py

CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!

GitHub Repository: jackfrued/Python-100-Days
Path: blob/master/Day16-20/code/example02.py
Views: ⁷²⁹
1
"""
2
排序 - 冒泡排序、选择排序、归并排序、快速排序
3
冒泡排序 - O(n ** 2)：两两比较，大的下沉
4
35, 97, 12, 68, 55, 73, 81, 40
5
35, 12, 68, 55, 73, 81, 40, [97]
6
12, 35, 55, 68, 73, 40, [81]
7
12, 35, 55, 68, 40, [73]
8
...
9
选择排序 - O(n ** 2)：每次从剩下元素中选择最小
10
-----------------------------------------
11
归并排序 - O(n * log_2 n) - 高级排序算法
12
35, 97, 12, 68, 55, 73, 81, 40
13
[35, 97, 12, 68], [55, 73, 81, 40]
14
[35, 97], [12, 68], [55, 73], [81, 40]
15
[35], [97], [12], [68], [55], [73], [81], [40]
16
[35, 97], [12, 68], [55, 73], [40, 81]
17
[12, 35, 68, 97], [40, 55, 73, 81]
18
[12, 35, 40, 55, 68, 73, 81, 97]
19
-----------------------------------------
20
快速排序 - 以枢轴为界将列表中的元素划分为两个部分，左边都比枢轴小，右边都比枢轴大
21
35, 97, 12, 68, 55, 73, 81, 40
22
35, 12, [40], 68, 55, 73, 81, 97
23
[12], 35, [40], 68, 55, 73, 81, [97]
24
[12], 35, [40], 55, [68], 73, 81, [97]
25
[12], 35, [40], 55, [68], 73, [81], [97]
26
"""
27

28

29
class Person(object):
30
    """人"""
31

32
    def __init__(self, name, age):
33
        self.name = name
34
        self.age = age
35

36
    # def __gt__(self, other):
37
    #     return self.name > other.name
38

39
    def __str__(self):
40
        return f'{self.name}: {self.age}'
41

42
    def __repr__(self):
43
        return self.__str__()
44

45

46
def select_sort(origin_items, comp=lambda x, y: x < y):
47
    """简单选择排序"""
48
    items = origin_items[:]
49
    for i in range(len(items) - 1):
50
        min_index = i
51
        for j in range(i + 1, len(items)):
52
            if comp(items[j], items[min_index]):
53
                min_index = j
54
        items[i], items[min_index] = items[min_index], items[i]
55
    return items
56

57

58
# 函数的设计要尽量做到无副作用（不影响调用者）
59
# 9 1 2 3 4 5 6 7 8
60
# 9 2 3 4 5 6 7 8 1
61
# *前面的参数叫位置参数，传参时只需要对号入座即可
62
# *后面的参数叫命名关键字参数，传参时必须给出参数名和参数值
63
# *args - 可变参数 - 元组
64
# **kwargs - 关键字参数 - 字典
65
def bubble_sort(origin_items, *, comp=lambda x, y: x > y):
66
    """冒泡排序"""
67
    items = origin_items[:]
68
    for i in range(1, len(items)):
69
        swapped = False
70
        for j in range(i - 1, len(items) - i):
71
            if comp(items[j], items[j + 1]):
72
                items[j], items[j + 1] = items[j + 1], items[j]
73
                swapped = True
74
        if swapped:
75
            swapped = False
76
            for j in range(len(items) - i - 1, i - 1, -1):
77
                if comp(items[j - 1], items[j]):
78
                    items[j], items[j - 1] = items[j - 1], items[j]
79
                    swapped = True
80
        if not swapped:
81
            break
82
    return items
83

84

85
def merge_sort(items, comp=lambda x, y: x <= y):
86
    """归并排序"""
87
    if len(items) < 2:
88
        return items[:]
89
    mid = len(items) // 2
90
    left = merge_sort(items[:mid], comp)
91
    right = merge_sort(items[mid:], comp)
92
    return merge(left, right, comp)
93

94

95
def merge(items1, items2, comp=lambda x, y: x <= y):
96
    """合并（将两个有序列表合并成一个新的有序列表）"""
97
    items = []
98
    index1, index2 = 0, 0
99
    while index1 < len(items1) and index2 < len(items2):
100
        if comp(items1[index1], items2[index2]):
101
            items.append(items1[index1])
102
            index1 += 1
103
        else:
104
            items.append(items2[index2])
105
            index2 += 1
106
    items += items1[index1:]
107
    items += items2[index2:]
108
    return items
109

110

111
def quick_sort(origin_items, comp=lambda x, y: x <= y):
112
    """快速排序"""
113
    items = origin_items[:]
114
    _quick_sort(items, 0, len(items) - 1, comp)
115
    return items
116

117

118
def _quick_sort(items, start, end, comp):
119
    """递归调用划分和排序"""
120
    if start < end:
121
        pos = _partition(items, start, end, comp)
122
        _quick_sort(items, start, pos - 1, comp)
123
        _quick_sort(items, pos + 1, end, comp)
124

125

126
def _partition(items, start, end, comp):
127
    """划分"""
128
    pivot = items[end]
129
    i = start - 1
130
    for j in range(start, end):
131
        if comp(items[j], pivot):
132
            i += 1
133
            items[i], items[j] = items[j], items[i]
134
    items[i + 1], items[end] = items[end], items[i + 1]
135
    return i + 1
136

137

138
def main():
139
    """主函数"""
140
    items = [35, 97, 12, 68, 55, 73, 81, 40]
141
    # print(bubble_sort(items))
142
    # print(select_sort(items))
143
    # print(merge_sort(items))
144
    print(quick_sort(items))
145
    items2 = [
146
        Person('Wang', 25), Person('Luo', 39),
147
        Person('Zhang', 50), Person('He', 20)
148
    ]
149
    # print(bubble_sort(items2, comp=lambda p1, p2: p1.age > p2.age))
150
    # print(select_sort(items2, comp=lambda p1, p2: p1.name < p2.name))
151
    # print(merge_sort(items2, comp=lambda p1, p2: p1.age <= p2.age))
152
    print(quick_sort(items2, comp=lambda p1, p2: p1.age <= p2.age))
153
    items3 = ['apple', 'orange', 'watermelon', 'durian', 'pear']
154
    # print(bubble_sort(items3))
155
    # print(bubble_sort(items3, comp=lambda x, y: len(x) > len(y)))
156
    # print(merge_sort(items3))
157
    print(merge_sort(items3))
158

159

160
if __name__ == '__main__':
161
    main()
162

163
CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!

Product

Resources

Company
