一、算法
1、算法概念
算法就是计算机解决问题的方法或者步骤
程序 = 数据结构 + 算法
2、算法的特性
①确定性：
算法的每条语句具有明确的意思，不能模棱两可
②有穷性：
在执行一定的时间后，能自动结束算法
③输入：
至少有0个或者多个的输入
④输出：
至少要有一个输出
⑤可行性：
经济可行，社会可行
3、算法的设计要求
①正确性：
对于正确的输入，会给出正确的结果。
②健壮性：
对于错误的输入，要给出合理的处理
③可读性：
要代码有适当的注释，命名规范
④高效率：
要求时间复杂度尽可能低
⑤低存储：
空间复杂度尽可能低
4、算法时间复杂度（T(n)）
①算法时间复杂度计算公式：
T(n) = O(f(n));
T(n):时间复杂度
n:表示问题的规模
f(n) :是问题规模与执行次数之间的函数
O(f(n)):使用O阶记法，记录算法时间复杂度
②时间复杂度推导
def fun1():
print("你好")
print("你好")
print("你好")
def fun2():
i = 0
while i<5:
print("你好")
i+=1
def fun3():
i = 0
while i<5:
print("你好")
j=0
while j<5:
print("你好")
j+=1
i+=1
fun1()
fun2()
fun3()
③常见的时间复杂度
二、排序算法
1、概念
定义：将给定的序列，按照特定的顺序进行排列的一种算法
种类：
①交换类排序：
冒泡排序、快速排序
②选择类排序：
简单选择排序、堆排序
③插入类排序：
直接插入排序、折半插入排序、希尔排序
④归并排序：
二路归并、三路归并。。。
⑤基数排序
2、冒泡排序
①概念和原理：
冒泡排序：是一种简单的排序算法，它重复的遍历要排序的序列，一次比较两个元素，如果他们的顺序错误，就把他们交换过来。
冒泡排序算法的运作如下：
- 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
②时间复杂度：O(n^2)
③算法实现：
#定义冒泡函数
def bubble_sort(alist):
j=0
while j<len(alist): #确定序列中数据
i=0
while i<len(alist)-1-j: #一个序列中两两比较的次数
if alist[i] > alist[i+1]: #前一个元素比后一个元素大 交互
alist[i],alist[i+1] = alist[i+1],alist[i]
i+=1
j+=1
# i=0
# while i<7:
# if alist[i] > alist[i+1]:
# alist[i],alist[i+1] = alist[i+1], alist[i]
# i+=1
#
# i = 0
# while i < 6:
# if alist[i] > alist[i + 1]:
# alist[i], alist[i + 1] = alist[i + 1], alist[i]
# i += 1
li = [54,26,93,17,77,31,44,55,20]
bubble_sort(li)
print(li)
3、选择排序
①概念和原理：
选择排序：选择出当前序列中最小或者最大元素的所在的下标，再将最小元素和第一个位置交换（再将最大元素和最后一个位置交换），再找出剩下元素中最小或者最大元素的所在的下标，再将最小元素和第二个位置交换（再将最大元素和最后二个位置交换），以此类推
②时间复杂度：O(n^2)
③算法实现：
#定义选择排序算法
def select_sort(alist):
i = 0 #当前序列中的第一个元素
while i<len(alist)-1:
min_idex = i #min_idex最小元素所在的下标 一开始就把第一个元素当成最小的
j = i+1 #使用j遍历当前序列中后面所有的元素
while j<len(alist):
if alist[min_idex] > alist[j]: #alist[j] < alist[min_idex]
min_idex = j
j+=1
if min_idex != i:
#将min_idex下标的元素放到第i位置上 交互
alist[i],alist[min_idex] = alist[min_idex],alist[i]
i+=1
# i = 1 # 当前序列中的第一个元素
# min_idex = i # min_idex最小元素所在的下标 一开始就把第一个元素当成最小的
# j = i + 1 # 使用j遍历当前序列中后面所有的元素
# while j < len(alist):
# if alist[min_idex] > alist[j]: # alist[j] < alist[min_idex]
# min_idex = j
# j += 1
# if min_idex != i:
# pass
li = [54,26,93,17,77,31,44,55,20]
select_sort(li)
print(li)4、直接插入排序 （抓牌）
①概念和原理：
- 定义：每次将待排序中的第一个元素，放入已排序列表中对应的位置
- 原理：每一步从待排序列中选取第一个元素，将其插入到之前已排序序列中，直到待排序列所有元素排完，则结束排序
②时间复杂度：O(n^2)
③算法实现：
#定义直接插入排序算法
def insert_sort(alist):
i = 1 #记录待排序列中的第一个位置 从第二个元素开始
while i < len(alist):
temp = alist[i]
j = i
while temp < alist[j-1] and j>0: #如果当前这个元素比前面的元素小
#前面的元素后移
alist[j] = alist[j-1]
j-=1
alist[j] = temp #将当前要插入的位置 将值赋值进来
i+=1
li = [54,26,93,17,77,31,44,55,20]
insert_sort(li)
print(li)5、快速排序
①概念和原理：
定义：快速排序是在序列元素与选定基准比较分割为大小两个部分的排序
基准（piovt）
原理：
- 从待排序列中，选定一个基准
- 以此为基准，将待排序列分为大小两个部分
- 对每个部分，再次选择一个基准，进行上述操作
- 直到每一个部分只有一个元素时，则排序成功
②时间复杂度：O(n^2)
③算法实现：
#定义第一趟快排函数
def part(alist,L,R):
#定义基准
p = alist[L]
while L<R:
while alist[R]>=p and L<R:
R-=1
alist[L] = alist[R] #将比基准小的数据放在左边
while alist[L] <= p and L<R:
L+=1
alist[R] = alist[L] #将比基准大的数据放在右边
#当L==R 说明只剩最后一个元素-->基准，L或者R就是基准所在的位置
alist[L] = p
return L #基准所在的下标
#定义快排函数
def quick_sort(alist,L,R):
if L<R:
#进行第一次快排，
p_idex = part(alist,L,R)
#将基准左侧的序列再次进行快排
quick_sort(alist,L,p_idex-1)
#将基准右侧的序列再次进行快排
quick_sort(alist,p_idex+1,R)
li = [54,26,93,17,77,31,44,55,20]
quick_sort(li,0,len(li)-1)
print(li)6、希尔排序
①概念和原理：
希尔排序是插入排序的一种，也称为缩小量排序。
原理：将序列在一个表中并对序列分别进行插入排序，重复过程，不过每次用更长的序列（步长更长了，列数更少了）
②时间复杂度：O(n^2)
③算法实现
#定义希尔排序算法
def shell_sort(alist):
#获取元素总个数
n=len(alist)
#设置初始步长
gap = n//2
while gap > 0:
#按步长进行插入
for i in range(gap,n):
j = i
while j>=gap and alist[j-gap] > alist[j]:
alist[j-gap],alist[j] = alist[j],alist[j-gap]
j-=gap
#更新步长
gap = gap // 2
alist = [49,58,65,97,26,13,27,49,55,4]
shell_sort(alist)
print(alist)
7、归并排序
①概念和原理：
定义：快速排序是在序列元素与选定基准比较分割为大小两个部分的排序
基准
原理：
- 从待排序列中，选定一个基准
- 以此为基准，将待排序列分为大小两个部分
- 对每个部分，再次选择一个基准，进行上述操作
- 直到每一个部分只有一个元素时，则排序成功
②时间复杂度：O(log n)
③算法实现：
def merge_sort(arr):
# 如果数组长度小于等于1，直接返回
if len(arr) <= 1:
return arr
# 分解
mid = len(arr) // 2
left_half = merge_sort(arr[:mid]) # 递归对左半部分排序
right_half = merge_sort(arr[mid:]) # 递归对右半部分排序
# 合并
return merge(left_half, right_half)
def merge(left, right):
merged = [] # 存储合并后的结果
i = j = 0
# 合并两个有序数组
while i < len(left) and j < len(right):
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:])
return merged
# 测试
arr = [8, 4, 5, 7, 1, 3, 6, 2]
sorted_arr = merge_sort(arr)
print("排序后的数组：", sorted_arr)