Python算法实践Week5-排序算法
0x01 选择排序
排序是计算机最为常见的操作之一，排序就是将一组杂乱无章的数据按照一定的规律排序起来（递增或递减），排序的对象可以是数字型，也可以是字符型（按照ASCII码的顺序排列）
- 选择排序（升序）
每次在若干无序数据中查找最小数，放在无序数据的首位
- 从
N个元素的列表中找最小值及下标，与第一个元素交换 - 从第二个元素开始的
N-1个元素中找出最小值及其下标，与第二个元素交换 - 以此类推，
N-1轮后即为排好序的数据
- 从
- 选择排序算法的实现
# 选择排序
list = [49, 38, 65, 97, 76, 13, 27, 49]
for i in range(len(list) - 1):
m = i
for j in range(i + 1, len(list)):
if list[j] < list[m]:
m = j
list[i], list[m] = list[m], list[i]
print(list)- 算法分析
选择排序共需比较
N-1轮，总共比较的轮数为(N-1)+(N-2)+...+2+1=N(N-1)/2次
选择排序执行交换的次数是N-1次
0x02 冒泡排序
- 算法思想
- 第一轮比较：从第一个元素开始，按照顺序对列表中所有
N个元素中连续的两个元素进行两两比较，如果两者不满足升序关系则交换。第一轮比较过后，最大数将下沉到列表最后。 - 第二轮比较：从第一个元素开始，对列表中前
N-1个元素之间进行两两比较，使第二大的数字沉到最后 - 以此类推，N-1轮后，排序完毕
- 第一轮比较：从第一个元素开始，按照顺序对列表中所有
- 冒泡排序算法的实现
list = [77, 42, 35, 10, 22, 101, 5]
for i in range(len(list) - 1):
for j in range(len(list) - 1 - i):
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j + 1], list[j]
print(list)- 冒泡排序算法的改进 如果在某一轮的比较中，一次交换也没有执行过，就说明已经排好序了
# 改进
list = [77, 42, 35, 10, 22, 101, 5]
for i in range(len(list) - 1):
flag = True
for j in range(len(list) - 1 - i):
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j + 1], list[j]
flag = False
if flag:
break
print(list)- 冒泡算法的分析
- 算法主要时间消耗是比较的次数
- 冒泡算法共需比较
N-1轮，总共比较次数为(N-1)+(N-2)+...+2+1=N(N-1)/2次 - 冒泡排序执行交换的次数不确定
- 冒泡排序是一种执行效率很低的排序算法
0x03 函数、递归
- 函数的好处
- 在程序中分离不同的任务
- 实现结构化程序设计
- 减少程序复杂度
- 实现代码的复用
- 提高代码的质量
- 协作开发
- 实现特殊功能(递归)
- .......
- Python中函数的分类
- 内置函数 input()、print()、int()、float()、len()、max()等
- 标准库函数 math包中的sqrt()、sin()、cos();random包中的random()等
- 第三方库函数
- 自定义库函数
- 函数
# 自定义函数的定义
def 函数名([形参列表]):
函数体
# 函数的调用
函数名([实参列表])
# 例子：定义一个求平均值的函数
def average(a, b):
return (a + b / 2)
temp = average(1, 3)
print(temp)- 问题：编写一个函数判断一个数是否为素数，并调用其输出200以内的素数
import math
def isPrime(a):
m = int(math.sqrt(a))
for i in range(2, m + 1):
if a % i == 0:
return False
return True
for i in range(2, 200):
if isPrime(i):
print(i)- 问题：将冒泡排序算法写成函数形式
def bubbleSort(a):
for i in range(len(a) - 1):
for j in range(len(a) - 1 - i):
if a[j] > a[i]:
a[j], a[i] = a[i], a[j]
list = [77, 42, 35, 10, 22, 101, 5]
bubbleSort(list)
print(list)- 递归函数 自调用函数，在函数体内部直接或间接调用自己
# 非递归方法
def factorial(n):
s = 1
for i in range(1, n + 1):
s = s * i
return s
# 递归方法
def factorial(n):
if n == 1:
return 1
else:
s = n * factorial(n - 1)
return s
print(factorial(3))
0x04 归并排序
- 算法思想
- 将包含N个元素的列表拆分成两个含
N/2个元素的子列表 - 对两个子列表递归调用归并排序(最后可将整个列表分为
N个子列表) - 合并两个已经排序好的子列表
- 将包含N个元素的列表拆分成两个含
- 归并排序算法的实现
def merge(left, right): # 合并两个列表
merged = []
i, j = 0, 0 # i和j分别作为left和right的下标
left_len, right_len = len(left), len(right) # 分别获取左右列表的长度
while i < left_len and j < right_len: # 循环归并左右子列表元素
if left[i] <= right[j]:
merged.append(left[i]) # 归并左子列表元素
i += 1
else:
merged.append(right[j]) # 归并右子列表元素
j += 1
merged.extend(left[i:]) # 归并左子列表剩余元素
merged.extend(right[j:]) # 归并右子列表剩余元素
print(left, right, merged) # 跟踪调试
return merged # 返回归并好的列表
def mergeSort(a): # 归并排序
if len(a) <= 1: # 空或者只有一个元素，直接返回列表
return a
mid = len(a) // 2 # 列表中间位置
left = mergeSort(a[:mid]) # 归并排序左子列表
right = mergeSort(a[mid:]) # 归并排序右子列表
return merge(left, right) # 合并排好序的左右两个子列表
a = [98, 23, 11, 10, 33, 42]
temp = mergeSort(a)
print(temp)python语言系统提供的排序算法，底层就采用了归并排序算法实现
a = sorted([24, 8, 10, 35])
print(a)
# [8, 10, 24, 35]
a.sort(reverse=True)
print(a)
# [35, 24, 10, 8]
b = sorted(a)
print(b)
# [8, 10, 24, 35]
c = sorted(a, reverse=True)
print(c)
# [35, 24, 10, 8]本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
