一、算法
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 = 0while i<5:print("你好")i+=1def fun3():i = 0while i<5:print("你好")j=0while j<5:print("你好")j+=1i+=1fun1()
fun2()
fun3()
③常见的时间复杂度
二、排序算法
1、概念
定义：将给定的序列，按照特定的顺序进行排列的一种算法
种类：
①交换类排序：
冒泡排序、快速排序
②选择类排序：
简单选择排序、堆排序
③插入类排序：
直接插入排序、折半插入排序、希尔排序
④归并排序：
二路归并、三路归并。。。
⑤基数排序
2、冒泡排序
①概念和原理：
冒泡排序：是一种简单的排序算法，它重复的遍历要排序的序列，一次比较两个元素，如果他们的顺序错误，就把他们交换过来。
冒泡排序算法的运作如下：
- 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
②时间复杂度：O(n^2)
③算法实现：
#定义冒泡函数
def bubble_sort(alist):j=0while j<len(alist): #确定序列中数据i=0while i<len(alist)-1-j: #一个序列中两两比较的次数if alist[i] > alist[i+1]: #前一个元素比后一个元素大 交互alist[i],alist[i+1] = alist[i+1],alist[i]i+=1j+=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 += 1li = [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 = jj+=1if 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:# passli = [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 = iwhile temp < alist[j-1] and j>0: #如果当前这个元素比前面的元素小#前面的元素后移alist[j] = alist[j-1]j-=1alist[j] = temp #将当前要插入的位置 将值赋值进来i+=1li = [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-=1alist[L] = alist[R] #将比基准小的数据放在左边while alist[L] <= p and L<R:L+=1alist[R] = alist[L] #将比基准大的数据放在右边#当L==R 说明只剩最后一个元素-->基准，L或者R就是基准所在的位置alist[L] = preturn 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//2while gap > 0:#按步长进行插入for i in range(gap,n):j = iwhile j>=gap and alist[j-gap] > alist[j]:alist[j-gap],alist[j] = alist[j],alist[j-gap]j-=gap#更新步长gap = gap // 2alist = [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) // 2left_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 += 1else: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)