七、排序与查找-上
1. 内容
- 顺序查找算法及分析
- 对有序表的二分查找算法及分析
- 冒泡排序和选择排序算法及分析
- 插入排序算法及分析
- 谢尔排序算法及分析（插入排序的进一步拓展）
- 归并排序算法及分析
- 快速排序算法及分析
2. 课程代码
在GitHub中下载
不同查找和排序算法的复杂度
3. OJ作业
所有代码均可在github中下载
3.1 快速排序主元
题目内容：
? ?著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元（中值），通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。 给定划分后的N个互不相同的非负整数的排列，请问有多少个元素可能是划分前选取的主元？
? ?例如给定的排列是[1, 3, 2, 4, 5]。则：
? ?1 的左边没有元素，右边的元素都比它大，所以它可能是主元；
? ?尽管 3 的左边元素都比它小，但其右边的 2 比它小，所以它不能是主元；
? ?尽管 2 的右边元素都比它大，但其左边的 3 比它大，所以它不能是主元；
? ?类似原因，4 和 5 都可能是主元。
? ?因此，有 3 个元素可能是主元。
输入格式: 一行数个整数的排列，由空格分隔
输出格式： 在第 1 行中输出有可能是主元的元素个数；在第 2 行中按递增顺序输出这些元素，其间以 1 个空格分隔，行首尾不得有多余空格（若元素个数为0则第二行为一行空行）。
输入样例：
1 3 2 4 5
输出样例：
3
1 4 5
方法：左右两侧设置两个列表 left_max 和 right_min 左边最大的一个数 右边最小的一个数 保存在两个列表。然后遍历列表中每一个数，如果当前数比他所在位置的left_max大，right_min小，则是主元。可以将遍历找主元和左侧最大数合并为一个循环
def main_point(in_list):
right_min = [0]*len(in_list) # 储存右侧最小数的列表
min_num = in_list[-1]
right_min[-1] = in_list[-1]
for i in range(len(in_list)-2, -1, -1): # [n-1, 1]
if in_list[i+1] <= min_num: # 如果当前的值小于min_num 则更新min_num值
min_num = in_list[i+1]
right_min[i] = min_num # 记录每一位的右侧最小值
# print(right_min) # 检验
left_max = in_list[0]
main_point_list = [] # 记录主元
for i in range(len(in_list)):
if left_max <= in_list[i] <= right_min[i]: # 判断是否为主元
main_point_list.append(in_list[i])
if left_max <= in_list[i]:
left_max = in_list[i] # 更新左侧最大数
main_point_list.sort()
print(len(main_point_list))
if len(main_point_list) > 0:
string = ' '.join(str(i) for i in main_point_list)
print(string)
else:
print()
return
in_list = list(map(int, input().split()))
main_point(in_list)
3.2 第一个坏版本
题目内容：
? ?现在有同一个产品的N个版本，编号为从1至N的整数；其中从某个版本之后所有版本均已损坏。现给定一个函数isBadVersion，输入数字N可判断该版本是否损坏（若损坏将输出True）；请找出第一个损坏的版本。
注：有时isBadVersion函数运行速度很慢，请注意优化查找方式
输入格式: 两行
? ?第一行为整数，为产品号总数N
? ?第二行为给定的判断函数，使用有效的Python表达式给出，可使用eval读取
输出格式：一行数字，表示第一个损坏的版本
输入样例：
50
lambda n:n>=30
输出样例：
30
方法：
? ?使用二分查找，找到中点，如果中间数n输出正确，若n-1错误，n为第一个错误版本， 若n-1正确，取中间数左边继续查找
? ?如果中间数n输出错误 若n+1正确，n+1为第一个错误版本，若n+1错误，取中间数右边继续查找
? ?样例4运行时间超过
代码
N = int(input())
isBadVersion = eval(input())
def firstBadVersion(n):
found = False
start = 0
end = n-1
version_num = 0
while start <= end and not found:
current_n = (start+end)//2
current_n = current_n+1 # 版本号
if isBadVersion(current_n): # n错误
if not isBadVersion(current_n-1): # n-1 正确
version_num = current_n # 找到
found = True
else: # n-1 错误 缩小范围在左边找
end = current_n-1
else: # n正确
if isBadVersion(current_n+1): # n+1错误
version_num = current_n+1
found = True
else: # n+1正确
start = current_n+1 # 缩小范围，在右边找
return version_num
print(firstBadVersion(N))
3.3 插入与归并
题目内容：
? ?给出如下定义：
? ?插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
? ?归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。
? ?现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？
输入格式:
两行由空格分隔的数字，其对应长度相等的列表
其中第一行代表未排序的列表，第二行是排序算法过程中某一步的中间列表
输出格式：
首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格
输入样例：
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
输出样例：
Merge Sort
1 2 3 8 4 5 7 9 0 6
输入样例2：
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
输出样例2：
Insertion Sort
1 2 3 5 7 8 9 4 6 0
方法：对于插入排序，插入好的部分是有序的，没有插入的部分和原序列保持一致
题中没有说是升序还是降序排列
代码：
sort_name = ['Insertion Sort', 'Merge Sort'] # 两种排序方式的名字
def jude_sort(in_list, sorted_list):
# 判断是什么排序方式
split_index = len(in_list)-1
for i in range(len(in_list)-1, 0, -1): # [n-1, 1] 从右往左遍历
if in_list[i] != sorted_list[i]: # 如果两个不相等，则找到了插入的分界点
split_index = i
break
sort_version = 'false'
stop = False
ascending_flag = True # 排序的升序排列标志
gap = 0 # 归并排序时，当前排序好的子列表长度
if sorted_list[split_index-1] <= sorted_list[split_index]: # 升序
for k in range(0, split_index): # [0, split_index-1]
if sorted_list[k] > sorted_list[k+1]: # 出现降序，说明是归并
sort_version = sort_name[1]
gap = k+1
break
else: # 一直升序，说明就是插入排序
sort_version = sort_name[0]
stop = True # 用来解决等于的情况 等于的时候有可能升序有可能降序，如果进入了else说明就是升序，那么就不再需要进入第二个if进行判断
if sorted_list[split_index-1] >= sorted_list[split_index] and not stop: # 降序
for k in range(0, split_index): # [0, split_index-1]
if sorted_list[k] < sorted_list[k+1]: # 出现升序，说明是归并
sort_version = sort_name[1]
gap = k+1
break
else: # 一直降序，说明就是插入排序
sort_version = sort_name[0]
ascending_flag = False
print(sort_version)
# 获取下一步排序队列
if sort_version == 'Insertion Sort':
current_value = in_list[split_index+1] # 现在需要排序的值
position = split_index+1 # 当前需要排序的位置
while position > 0 and (sorted_list[position-1] > current_value) == ascending_flag:
sorted_list[position] = sorted_list[position-1]
position = position-1
sorted_list[position] = current_value
elif sort_version == 'Merge Sort': # 现以2gap排序
group_num = len(in_list) // (2*gap) # 有多少个2gap
for j in range(group_num): # 归并
left_list = sorted_list[j*2*gap: j*2*gap+gap] # [0, 1]
right_list = sorted_list[j*2*gap+gap: (j+1)*2*gap] # [2, 3]
r = j*2*gap
p = q = 0
while p < len(left_list) and q < len(right_list):
if (left_list[p] < right_list[q]) == ascending_flag:
sorted_list[r] = left_list[p]
p = p+1
else:
sorted_list[r] = right_list[q]
q = q+1
r = r+1
while p < len(left_list):
sorted_list[r] = left_list[p]
p = p+1
r = r+1
while q < len(right_list):
sorted_list[r] = right_list[q]
q = q+1
r = r+1
# 处理剩下的不足2gap的部分
if len(sorted_list[group_num*2*gap:]) <= gap: # 剩余部分小于等于gap，不变
pass
elif gap < len(sorted_list[group_num*2*gap:]) <= 2*gap: # 剩余部分在gap，2gap之间，需要进行拉链排序合并
left_list = sorted_list[group_num*2*gap: group_num*2*gap+gap]
right_list = sorted_list[group_num*2*gap:]
r = group_num*2*gap
p = q = 0
while p < len(left_list) and q < len(right_list):
if (left_list[p] < right_list[q]) == ascending_flag:
sorted_list[r] = left_list[p]
p = p+1
else:
sorted_list[r] = right_list[q]
q = q+1
r = r+1
while p < len(left_list):
sorted_list[r] = left_list[p]
p = p+1
r = r+1
while q < len(right_list):
sorted_list[r] = right_list[q]
q = q+1
r = r+1
else:
print('false')
string = ' '.join(str(item) for item in sorted_list)
print(string)
return
in_list = list(map(int, input().split())) # 原序列
sorted_list = list(map(int, input().split())) # 排序若干步后序列
jude_sort(in_list, sorted_list)