"""
排序 - 冒泡排序、选择排序、归并排序、快速排序
冒泡排序 - O(n ** 2):两两比较,大的下沉
35, 97, 12, 68, 55, 73, 81, 40
35, 12, 68, 55, 73, 81, 40, [97]
12, 35, 55, 68, 73, 40, [81]
12, 35, 55, 68, 40, [73]
...
选择排序 - O(n ** 2):每次从剩下元素中选择最小
-----------------------------------------
归并排序 - O(n * log_2 n) - 高级排序算法
35, 97, 12, 68, 55, 73, 81, 40
[35, 97, 12, 68], [55, 73, 81, 40]
[35, 97], [12, 68], [55, 73], [81, 40]
[35], [97], [12], [68], [55], [73], [81], [40]
[35, 97], [12, 68], [55, 73], [40, 81]
[12, 35, 68, 97], [40, 55, 73, 81]
[12, 35, 40, 55, 68, 73, 81, 97]
-----------------------------------------
快速排序 - 以枢轴为界将列表中的元素划分为两个部分,左边都比枢轴小,右边都比枢轴大
35, 97, 12, 68, 55, 73, 81, 40
35, 12, [40], 68, 55, 73, 81, 97
[12], 35, [40], 68, 55, 73, 81, [97]
[12], 35, [40], 55, [68], 73, 81, [97]
[12], 35, [40], 55, [68], 73, [81], [97]
"""
class Person(object):
"""人"""
def __init__(self, name, age):
self.name = name
self.age = age
# def __gt__(self, other):
# return self.name > other.name
def __str__(self):
return f'{self.name}: {self.age}'
def __repr__(self):
return self.__str__()
def select_sort(origin_items, comp=lambda x, y: x < y):
"""简单选择排序"""
items = origin_items[:]
for i in range(len(items) - 1):
min_index = i
for j in range(i + 1, len(items)):
if comp(items[j], items[min_index]):
min_index = j
items[i], items[min_index] = items[min_index], items[i]
return items
# 函数的设计要尽量做到无副作用(不影响调用者)
# 9 1 2 3 4 5 6 7 8
# 9 2 3 4 5 6 7 8 1
# *前面的参数叫位置参数,传参时只需要对号入座即可
# *后面的参数叫命名关键字参数,传参时必须给出参数名和参数值
# *args - 可变参数 - 元组
# **kwargs - 关键字参数 - 字典
def bubble_sort(origin_items, *, comp=lambda x, y: x > y):
"""冒泡排序"""
items = origin_items[:]
for i in range(1, len(items)):
swapped = False
for j in range(i - 1, len(items) - i):
if comp(items[j], items[j + 1]):
items[j], items[j + 1] = items[j + 1], items[j]
swapped = True
if swapped:
swapped = False
for j in range(len(items) - i - 1, i - 1, -1):
if comp(items[j - 1], items[j]):
items[j], items[j - 1] = items[j - 1], items[j]
swapped = True
if not swapped:
break
return items
def merge_sort(items, comp=lambda x, y: x <= y):
"""归并排序"""
if len(items) < 2:
return items[:]
mid = len(items) // 2
left = merge_sort(items[:mid], comp)
right = merge_sort(items[mid:], comp)
return merge(left, right, comp)
def merge(items1, items2, comp=lambda x, y: x <= y):
"""合并(将两个有序列表合并成一个新的有序列表)"""
items = []
index1, index2 = 0, 0
while index1 < len(items1) and index2 < len(items2):
if comp(items1[index1], items2[index2]):
items.append(items1[index1])
index1 += 1
else:
items.append(items2[index2])
index2 += 1
items += items1[index1:]
items += items2[index2:]
return items
def quick_sort(origin_items, comp=lambda x, y: x <= y):
"""快速排序"""
items = origin_items[:]
_quick_sort(items, 0, len(items) - 1, comp)
return items
def _quick_sort(items, start, end, comp):
"""递归调用划分和排序"""
if start < end:
pos = _partition(items, start, end, comp)
_quick_sort(items, start, pos - 1, comp)
_quick_sort(items, pos + 1, end, comp)
def _partition(items, start, end, comp):
"""划分"""
pivot = items[end]
i = start - 1
for j in range(start, end):
if comp(items[j], pivot):
i += 1
items[i], items[j] = items[j], items[i]
items[i + 1], items[end] = items[end], items[i + 1]
return i + 1
def main():
"""主函数"""
items = [35, 97, 12, 68, 55, 73, 81, 40]
# print(bubble_sort(items))
# print(select_sort(items))
# print(merge_sort(items))
print(quick_sort(items))
items2 = [
Person('Wang', 25), Person('Luo', 39),
Person('Zhang', 50), Person('He', 20)
]
# print(bubble_sort(items2, comp=lambda p1, p2: p1.age > p2.age))
# print(select_sort(items2, comp=lambda p1, p2: p1.name < p2.name))
# print(merge_sort(items2, comp=lambda p1, p2: p1.age <= p2.age))
print(quick_sort(items2, comp=lambda p1, p2: p1.age <= p2.age))
items3 = ['apple', 'orange', 'watermelon', 'durian', 'pear']
# print(bubble_sort(items3))
# print(bubble_sort(items3, comp=lambda x, y: len(x) > len(y)))
# print(merge_sort(items3))
print(merge_sort(items3))
if __name__ == '__main__':
main()
没有合适的资源?快使用搜索试试~ 我知道了~
python课程设计第16-20天,python-Day16-20.rar
共31个文件
py:28个
png:2个
md:1个
需积分: 5 0 下载量 181 浏览量
2024-05-11
07:12:40
上传
评论
收藏 185KB RAR 举报
温馨提示
python课程设计第16-20天,python-Day16-20.rar
资源推荐
资源详情
资源评论
收起资源包目录
python-Day16-20.rar (31个子文件)
Day16-20
Python语言进阶.md 46KB
res
algorithm_complexity_1.png 73KB
algorithm_complexity_2.png 96KB
code
example06.py 1KB
example17.py 1KB
example04.py 1KB
homework02.py 1KB
homework01.py 938B
example19.py 3KB
example21.py 2KB
example16.py 2KB
example22.py 1011B
test_example02.py 686B
test_example01.py 2KB
example20.py 821B
example15.py 2KB
example01.py 2KB
example07.py 1KB
example14.py 2KB
example24.py 1KB
example11.py 495B
example23.py 1010B
example18.py 1KB
example05.py 1KB
example02.py 5KB
example10.py 938B
example13.py 419B
example09.py 2KB
example03.py 1KB
example12.py 2KB
example08.py 1KB
共 31 条
- 1
资源评论
流华追梦
- 粉丝: 5047
- 资源: 2221
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功