一、初等排序
1.插入排序法
1.1 任务要求
请用python编写一个程序，用插入排序法将包含N个元素（用户自行输入）的数列按升序排列。为检验算法的执行过程，请输出各计算步骤的数组(完成输入后的数组，以及每次执行自增后的数组)。
1.2 解题思路（每次将一个未排序的元素依次循环根据大小插到已排序的元素列表内）
将开头元素视作已排序，然后循环依次取出还未排序部分的开头元素赋值给num，在已排序部分将所有比num大的元素向后依次移动一个单位，将原已取出的元素num插入最后已排序元素移动后的空位。
1.3 代码及结果
b = [] a = input() # 输入 for x in a: # 将字符串转换成列表 b.append(x) for i in range(len(b)): num = b[i] j = i-1 # j是已排序元素的列表索引 while(j >= 0 and b[j] > num): # 比较后对已排序部分进行往后依次移动 b[j+1] = b[j] j -= 1 b[j+1] = num # 插入空位 print(b) # 输出
2.冒泡排序法
2.1 任务要求
请用python编写一个程序，读取数列并利用冒泡排序法将其按升序排列并输出，另外请输出冒泡排序法执行元素交换的次数。
2.2 解题思路（从末尾元素开始循环每次比较相邻元素大小再交换位置，实现每次循环都找到未排序元素中的最小元素并将其排序到前头已排序元素列表）
同样分已排序和未排序部分，从数组末尾开始依次比较相邻两个元素，如果大小关系相反则交换位置，每次循环都确定左边已排序一个元素，最终完成冒泡排序（小->大）。
2.3 代码及结果
b = [] a = input() # 输入 count = 0 for x in a: b.append(x) for i in range(len(b)): # 冒泡排序 j = len(b) - 1 # 从末尾开始准备比较 while(j != i): # 保证不重复比较已排序的元素 if b[j - 1] > b[j]: # 未排序部分左边元素大于右边相邻元素则交换位置，然后继续相邻元素比较 num = b[j] b[j] = b[j - 1] b[j - 1] = num count += 1 j -= 1 print(b) # 输出排序结果 print(count) #输出排序次数
3.选择排序法
3.1 任务要求
请用python编写一个程序，读取数列并利用选择排序法将其按升序排列并输出，另外请输出选择排序法执行元素交换的次数。
3.2 解题思路（每次循环将未排序部分起始元素作为初未排序部分的最小值，然后通过和未排序元素依次比较记录真正未排序部分最小值的下标，然后将初未排序部分的最小值和真正未排序部分最小值进行交换，与冒泡排序相比选择排序无需每次比较后直接更换相邻元素）
同样分已排序和未排序，首先将每次循环中的未排序部分的起始元素视作初最小值元素，然后通过内循环依次比较大小找出未排序部分真正最小值元素的位置，将真正最小值的位置的元素和未排序部分的初最小值元素交换。
3.3 代码及结果
b = [] a = input() # 输入 count = 0 # 记录排序次数 for x in a: b.append(x) for i in range(len(b)): min = b[i] # 初最小值元素 j = i+1 flag = 0 # 排序结束标志 while(j < len(b)): if b[j] < min: flag = 1 min = b[j] w = j # 找到未排序部分真正最小值下标赋值给w j += 1 if flag: # 交换位置 z = b[i] b[i] = b[w] b[w] = z count += 1 else: break print(b) # 输出排序结果 print(count) # 输出排序次数
4.伪选择冒泡结合排序法（仅供参考，可跳）
4.1 任务要求
同初等排序问题2、3上
4.2 解题思路
每次将未排序部分开头元素视作最小值，然后在未排序部分进行循环比较依次交换位置，最后完成排序。
4.3 代码及结果
b = [] a = input() # 输入 count = 0 # 记录排序次数 for x in a: b.append(x) for i in range(len(b)): min = b[i] # 未排序部分开头元素设置成最小值 j = i+1 while(j < len(b)): # 依次比较交换固定最小值 if b[j] < min: b[i] = b[j] b[j] = min min = b[i] count += 1 j += 1 print(b) # 输出排序结果 print(count) #输出排序次数
5.希尔排序法
5.1 任务要求
请用python编写一个程序，读取间隔元素和需要排序的数列并利用希尔排序法将其按升序排列并输出。
5.2 解题思路（多个隔空值比较排序）
首先读取间隔元素列表和需排序元素列表，然后依次将间隔元素循环作为间距，再将循环需排序元素列表的起始下标的值设置成间隔元素大小，每次循环下以目标元素（初始化为该循环下间隔元素的位置下标，后面逐步加1往后移动）为起点，与目标元素前面间距为间隔元素的需排列元素进行依次比较（注意只向前看，不考虑向后看），若比较的需排列元素大于目标元素的值时需排列元素直接替换目标元素的位置，最后比较完后再补充目标元素的值，最后实现希尔排序。
5.3 代码及结果
b = list(map(int,input().split())) # 输入间隔元素列表 a = list(map(int,input().split())) # 输入排列元素列表 w = 0 while(w != len(b)): # 不同间隔元素每次循环排列 for i in range(b[w], len(a)): # 希尔排序 temp = a[i] # j = i - b[w] while (j >= 0 and a[j] > temp): # 判断目标元素与它间隔元素距离的元素大小进行小到大排序 a[j + b[w]] = a[j] j = j - b[w] a[j + b[w]] = temp # 补充目标元素的值 w += 1 print(a) # 输出排序结果
二、数据结构
1.栈结构（Stack）
1.1 结构特点
栈(Stack)是一种能有效帮助我们临时保存数据的数据结构，按照最后进入栈的数据最先出栈(Last In First Out，LIFO，后入先出或者先进后出)的规则管理数据。
1.2 构建思路
对于栈结构的构建是使用python的列表进行实现，入栈的过程使用python列表自带的函数append实现，元素是从列表头部开始加入，出栈的过程使用python列表自带的函数pop实现，pop函数默认取出列表的最末端元素，判断是否为空栈直接用python的bool函数，至于判断是否为满栈无需此操作，因为python列表初始化可以无限制大小，所以就不需要构建这个函数。
1.3 实现代码
class Stack: def __init__(self): self.stack = [] # 初始化启动构造函数定义一个空栈，也就是空列表 def push(self,x): # 将元素入栈 self.stack.append(x) def pop(self): # 将元素出栈 if self.stack: self.stack.pop() # 将列表最后一个元素取出 else: print("The stack is null !") def isempty(self): # 判断栈是否为空，为空返回True result = bool(1 - bool(self.stack)) return result s = Stack() # 创建栈对象 s.push(1) # 调用类入栈函数 s.pop() # 调用类出栈函数 print(s.isempty()) # 调用类判断栈是否为空函数并输出判断结果
2.队列结构（Queue）
2.1 结构特点
队列(Queue)也是一种能有效帮助我们临时保存数据的数据结构，与栈的规则恰好相反，按照先入队列的数据最先出队列(First In First Out，FIFO，先入先出)的规则管理数据。
2.2 构建思路
对于队列结构的构建是使用python的列表进行实现，入队的过程使用python列表自带的函数append实现，元素是从列表头部开始加入，出队的过程使用python列表自带的函数pop实现，pop函数不带参数时默认取出列表的最末端元素，但pop(0)表示从列表头部取出元素，判断是否为空队列直接用python的bool函数，至于判断是否为满队列无需这个，因为python列表初始化可以无限制大小，所以就不需要构建这个函数。
2.3 实现代码
class Queue: def __init__(self): # 创建队列 self.queue = [] def enterqueue(self,x): # 入队 self.queue.append(x) def delqueue(self): # 出队 if self.queue: # w = self.queue.pop(0) # return w self.queue.pop(0) # 先入先出 else: print("Queue is null !") def isEmpty(self): # 判断队列是否为空 result = bool(1 - bool(self.queue)) return result queue = Queue() # 创建队列类对象 for i in range(6): queue.enterqueue(i) # 将6个元素循环输入入队 # w = queue.delqueue() # print(w) queue.delqueue() # 将第一个入队元素取出 print(queue.isEmpty()) # 判断队列是否为空
3.链表结构（Doubly Linked List）
3.1 结构特点
链表(Doubly Linked List)也是一种能有效帮助我们临时保存数据的数据结构，表中各元素称作“结点”，结点由数据本体和指向下一个结点的指针next组成，这些结构体通过指针连接成一个链，从而能够高效的增删操作进行管理数据。
3.2 构建思路
对于链表结构的构建是使用python的列表进行转换实现，首先定义链表结点类，结点包含两部分：一部分是结点的数据本体，另一部分是结点的“指针”，但因为python没有指针，所以此“指针”非C/C++中定义的指针，而是实际表示下一个结点的实例对象。然后创建头结点和尾结点，注意的是头结点是不能随意改动因为一旦乱改动链表的值就可能会造成缺失，因为python中遍历链表是只能通过头结点依次连续获取链表的下个结点。链表实现结构是：头结点（数据本体+第二个结点（数据本体+第三个节点（数据本体+第四个结点（…（倒数第二个结点+（尾结点（None）））））））
3.3 实现代码
class linkNode(): """创建链结点的类""" def __init__(self,data): self.data = data # 结点的数据本体 self.next = None # 结点的指针，因python没有指针，所以此next实际表示下一个结点的实例对象 class Doublylinkedlist(): """"创建链表结构并定义操作函数""" def __init__(self,list): # 传入数组，将数组各元素转换成链表结构 self.length = len(list) # 数组长度 if self.length <= 0: # 判断数组是否为空，为空就不必转换成链表 print("The list is null !") return i = 0 # 数组下标，保证元素一个一个传递 self.head = linkNode(list[i]) # 表头结点 self.tail = self.head # 表尾结点，初始表头结点=表尾结点 i += 1 while i < self.length: # 保证传来的数组各元素都转换成结点并链接起来 # 表尾结点指针next指向下一个结点，也就是表示下一个节点的实例对象 self.tail.next = linkNode(list[i]) self.tail = self.tail.next # 表尾结点移动转换成下一个结点 i += 1 def insertNode(self,index,data): # 插入结点，提供结点要插入的位置和结点的数据本体 if index > self.length: # 首先判断要插入的结点位置是否满足原链表的长度内，否则无意义 print("The range is out !") return if index == 0: # 在下标为0的位置插入新结点，取代原头结点，而原头结点变成新头结点的下个结点 temp = linkNode(data) # 新头结点创建 temp.next = self.head self.head = temp self.length += 1 # 成功插入后链表长度加1 return if index == self.length: # 在下标为链表长度的位置插入新结点，是直接在链表末尾加入新结点 self.tail.next = linkNode(data) self.tail = self.tail.next self.length += 1 # 成功插入后链表长度加1 return # 最后一种情况在链表中间插入新结点 pointerlocation = self.head # 创建在链表中新结点要插入位置的前一个结点 while index > 1: # 首先根据下标index从链表头结点依次向后寻找新结点要插入位置的前一个结点 pointerlocation = pointerlocation.next index -= 1 temp = linkNode(data) # 创建新结点 temp.next = pointerlocation.next # 进行新结点插入操作 pointerlocation.next = temp self.length += 1 # 成功插入后链表长度加1 def getlinkedlength(self): # 获取链表的长度 print("The linked length = ",self.length) def printlinked(self): # 输出链表 if self.head == None: # 判断链表是否为空 print("The list is Null !") # 链表不为空时依次输出数据 temp = self.head while temp != None: # 遍历链表直到结束 print(temp.data,end=" ") # end=' '意思是末尾不换行，加空格 temp = temp.next num = [1,5,6,4,8] # 传入的列表转变成链表结构 result = Doublylinkedlist(num) # 构建链表，列表转变成链表结构 result.insertNode(1,10) # 插入元素 result.printlinked() # 输出链表
三、搜索
1.线性搜索法
1.1 概念定义
线性搜索就是从数组开头顺次访问各元素，检查该元素是否与目标值相等。若相等则返回该元素的位置并结束搜索。如果检查到数组末尾仍未发现目标值，则返回一个特殊值来说明该情况。虽线性搜索的算法效率很低，但适用于任何形式的数据。
1.2 任务要求
请用python编写一个程序，首先输人包含a个整数的数列S以及包含b个不重复整数的数列T，再用线性搜索法搜索并统计，最后输出既包含于T也包含于S的整数的个数C。
1.3 解题思路
创建两个数列（S和T）并分别接收外部输入的值，然后使用两个双循环从数列S开头顺序依次访问数列T并比较各元素的值是否相同，相同则计数加1，最后双循环结束后输出计数结果。
1.4 代码及结果
S = list(map(int,input().split())) # 输入创建数列S T = list(map(int,input().split())) # 输入创建数列T count = 0 # 统计S和T相同的元素的个数C for i in range(len(S)): # 线性搜索，依次循环比较 for j in range(len(T)): if S[i] == T[j]: count += 1 break print(count) # 输出结果C
2.二分搜索法
2.1 概念定义
二分搜索(二分查找)算法可以利用数据的大小进行高速搜索。现实中计算机管理数据时一般会根据特定项目对其进行排序，这就让二分搜索算法有了用武之地。与线性搜索法相比二分搜索每执行完一步搜索，范围都会减半，因此可以在极短时间内完成搜索任务。
2.2 任务要求
请用python编写一个程序，首先输人包含a个整数的数列S以及包含b个不重复整数的数列T，再用二分搜索法搜索并统计，最后输出既包含于T也包含于S的整数的个数C。
2.3 解题思路
1.将整个数组作为搜索范围。
2.检查位于搜索范围正中央的元素。
3.如果中央元素的关键字与目标关键字一致则结束搜索。
4.如果中央元素的关键字小于目标关键字，则以前半部分为搜索范围重新执行2，如果大于目标关键字，则以后半部分为搜索范围重新执行2。
2.4 代码及结果
S = list(map(int,input().split())) # 输入数列S T = list(map(int,input().split())) # 输入数列T count = 0 # 计数次数C for i in range(len(T)): flag = 1 # 匹配成功或者全部无法匹配就变成0结束下面的while循环 left = 0 # 左指针（数组下标） right = len(S) - 1 # 右指针（数组下标） while(flag): if(left >= right): # 全部无法匹配 flag = 0 mid = (left + right)//2 # 中间指针（数组下标），向下取整 # print(mid) if(T[i] == S[mid]): # T数列中的元素和中间指针的下标对应的S数列中的元素匹配上 flag = 0 count += 1 elif(T[i] > S[mid]): # T数列中的元素大于中间指针的下标对应的S数列中的元素 left = mid + 1 # 左指针则右移，缩小搜索范围 else: right = mid # 右指针则左移，缩小搜索范围 print(count) # 输出两数列匹配成功元素的个数
3.散列搜索法
3.1 概念定义
在散列法中，各元素的存储位置由散列函数决定。散列既是一种数据结构， 同时也是一种使用散列表的算法。这种算法只需将元素的关键字(值)代入特定函数便可找出其对应位置下标，对某些种类的数据有着极高的搜索效率。
3.2 任务要求
请用python编写一个程序，第一行输入命令行数N，随后N行按顺序输入N个命令，命令格式分为insert（添加元素）和find（寻找匹配元素），使用find命令则进行匹配，匹配成功输出yes，否则输出no，每个输出占一行。
3.3 解题思路
首先是获取输入的指令，再根据指令执行对应的添加和寻找匹配操作，最后实现正确输出。
3.4 代码及结果
d = list(map(int,input())) # 输入命令行的数目 num = d[0] a = [] for i in range(num): strs = list(map(str,input().split())) # 输入指令 if strs[0] == "insert": # 判断指令，并后续执行操作 a.append(strs[1]) else: flag = 1 for w in range(len(a)): if a[w] == strs[1]: flag = 0 # 匹配成功则直接输出并跳过此循环 print("yes") break if flag: print("no") # 没有匹配成功
四、递归和分治法
1.递归法
1.1 概念定义
递归函数就是指自己调用自己的函数，是设计算法时的一种编程技巧。
1.2 任务要求
请用python编写一个程序，使用递归函数实现计算整数num的阶乘的函数。
1.3 解题思路
递归就是循环嵌套计算。
1.4 代码及结果
def recursions(data): # 递归函数 if data == 1: return 1 else: return data * recursions((data-1)) # 递归过程 num = list(map(int,input().split())) # 输入 nums = num[0] print(recursions(nums)) # 输出
2.分治法
2.1 概念定义
分治法是使用递归的技巧，可以将一个问题拆分成两个或更多较小的局部问题，利用递归函数求出每个局部问题的解，然后再将结果整合，最终解决原问题，这种编程手法称为分治法，是设计算法时的一种编程技巧。
2.2 任务要求
请用python编写一个程序，使用分治法搜索出数组A中最大的元素并输出。
2.3 解题思路
首先将问题分割成局部问题，递归地求解局部问题，将局部问题的解“整合”，解决原问题。
2.4 代码及结果
def findmaxnum(a,l,r): m = (l + r) // 2 if l == r - 1: return a[l] else: left = findmaxnum(a,l,m) right = findmaxnum(a,m,r) maxnum = max(left,right) return maxnum a = list(map(int,input().split())) print(findmaxnum(a,0,len(a)))
3.穷举搜索法
3.1 概念定义
穷举搜索法，顾名思义是要穷举比较所有元素进行搜索，使用递归方法进行实现，也是设计算法时的一种编程技巧。
3.2 任务要求
请用python编写一个程序，输入数列a和整数数组m，判断a中任意几个元素相加是否能得到m，注意a中的每个元素只能使用一次，如果能成功匹配输出yes，否则输出no。
3.3 解题思路
首先肯定要采用递归方法，所有开始就将第一个元素利用递归函数创造“选择”和“不选择”的分支，这样产生一种树状组合，不断进行比较匹配，最后得出结果。
3.4 代码及结果
def solve(a,i,m): # 穷举搜索 if m == 0: # 凑数匹配成功 return 1 if i >= len(a): #无结果 return 0 else: resultpre = solve(a,i+1,m) # 不选择a[i]的元素 resultlas = solve(a,i+1,m-a[i]) # 选择a[i]的元素 result = resultlas + resultpre # 结果无非0和其他非零结果 return result a = list(map(int,input().split())) # 输入数组a m = list(map(int,input().split())) # 输入数组m flag = 0 for w in range(len(m)): # 循环比较 if m[w] == 0: # 数组m中不能输入0 print("m is not zero, input is wrong !") else: flag = solve(a, 0, m[w]) # 穷举递归 if flag: print("yes") else: print("no") flag = 0
