提出一个解决方法，帮彩民快速的从自己钟爱的数字产生的排列集合中找出已经中过奖的号码。以“21选5”为例，假定自己钟爱的数字产生的排列集合A以及前期中将号码的集合B里面的每一注号码，都由可以一个10个长度的数字字符串表示，两个集合里面的号码都由随即产生，号码注数都不少于5000个。
【基本要求】（1）输入数据包括：自己钟爱的数字产生的排列集合A，以及前期中将号码的集合B，都存储在输入文件input.txt中；输出集合A和集合B中相同的号码字符串,存放在output.txt。（2）集合A和B中的数据，号码字符串采用伪随机数的方式产生，每注中的5个数据不能重复。（3）采用多种比较算法来实现相同号码字符串的查找，至少使用选择排序（或冒泡排序），快速排序（或者合并排序），堆排序（或者希尔排序）并且统计比较次数。（4）在号码字符串的比较过程中，不能采用strcmp( )函数或者string类对象的方式比较，调用函数进行比较效率会比较低，建议将字符串转换成基本数据类型，例如int或者long类型进行比较。（5）要提示菜单的方式，显示使用了多种排序算法来进行两个集合元素的比较。
本题需要实现从集合A和集合B中查找相同的号码字符串，要求实现多种算法，并统计比较次数。因此，本解决方案将分以下几步进行： 1. 从输入文件input.txt中读取集合A和集合B； 2. 实现选择排序、快速排序和堆排序三种算法，并统计比较次数； 3. 将结果输出到文件output.txt。
根据上述思路，我们可以先定义一个 main() 函数，具体功能和步骤如下：
import numpy as np
def main():
# Step1：从输入文件input.txt中读取集合A和集合B
a = np.loadtxt('input.txt', delimiter=',', dtype=int, usecols=(0,))
b = np.loadtxt('input.txt', delimiter=',', dtype=int, usecols=(1,))
# Step2：调用选择排序、快速排序和堆排序三种算法，并统计比较次数
# 选择排序
a_sel_comp = 0
b_sel_comp = 0
a_sorted_sel, a_sel_comp = selectionSort(a, a_sel_comp)
b_sorted_sel, b_sel_comp = selectionSort(b, b_sel_comp)
# 快速排序
a_qck_comp = 0
b_qck_comp = 0
a_sorted_qck, a_qck_comp = quickSort(a, 0, len(a)-1, a_qck_comp)
b_sorted_qck, b_qck_comp = quickSort(b, 0, len(b)-1, b_qck_comp)
# 堆排序
a_heap_comp = 0
b_heap_comp = 0
a_sorted_heap, a_heap_comp = heapSort(a, a_heap_comp)
b_sorted_heap, b_heap_comp = heapSort(b, b_heap_comp)
# Step3：将结果输出到文件output.txt
out = open("output.txt", "w")
out.write("选择排序:\nA与B中相同的号码有：")
findSame(a_sorted_sel, b_sorted_sel, out)
out.write("\n比较次数：A中共计{}次，B中共计{}次\n\n".format(a_sel_comp, b_sel_comp))
out.write("快速排序:\nA与B中相同的号码有：")
findSame(a_sorted_qck, b_sorted_qck, out)
out.write("\n比较次数：A中共计{}次，B中共计{}次\n\n".format(a_qck_comp, b_qck_comp))
out.write("堆排序:\nA与B中相同的号码有：")
findSame(a_sorted_heap, b_sorted_heap, out)
out.write("\n比较次数：A中共计{}次，B中共计{}次".format(a_heap_comp, b_heap_comp))
out.close()
对于选择排序、快速排序和堆排序三个算法，代码实现如下：
# 选择排序
def selectionSort(arr, num_comp):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
num_comp += 1
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr, num_comp
# 快速排序
def partition(arr, low, high, num_comp):
i = low - 1
pivot = arr[high]
for j in range(low, high):
num_comp += 1
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1, num_comp
def quickSort(arr, low, high, num_comp):
if low < high:
pi, num_comp = partition(arr, low, high, num_comp)
num_comp += 1
quickSort(arr, low, pi-1, num_comp)
quickSort(arr, pi+1, high, num_comp)
return arr, num_comp
# 堆排序
def heapify(arr, n, i, num_comp):
largest = i
left = 2*i+1
right = 2*i+2
if left < n and arr[i] < arr[left]:
num_comp += 1
largest = left
if right < n and arr[largest] < arr[right]:
num_comp += 1
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest, num_comp)
return num_comp
def heapSort(arr, num_comp):
n = len(arr)
for i in range(n//2-1, -1, -1):
num_comp = heapify(arr, n, i, num_comp)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
num_comp = heapify(arr, i, 0, num_comp)
return arr, num_comp
最后是查找相同号码和输出到文件的代码：
# 查找相同号码
def findSame(A, B, out):
i = 0
j = 0
while i < len(A) and j < len(B):
if A[i] < B[j]:
i += 1
elif A[i] > B[j]:
j += 1
else:
out.write("{},".format(A[i]))
i += 1
j += 1
在 main() 函数中，我们按照步骤调用各个函数，并将结果输出到文件 output.txt 中。完整代码如下：
```python import numpy as np
def selectionSort(arr, num_comp): for i in range(len(arr)): min_idx = i for j in range(i+1, len(arr)): num_comp += 1 if arr[min_idx] > arr[j]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr, num_comp
def partition(arr, low, high, num_comp): i = low - 1 pivot = arr[high] for j in range(low, high): num_comp += 1 if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i+1], arr[high] = arr[high], arr[i+1] return i+1, num_comp
def quickSort(arr, low, high, num_comp): if low < high: pi, num_comp = partition(arr, low, high, num_comp) num_comp += 1 quickSort(arr, low, pi-1, num_comp) quickSort(arr, pi+1, high, num_comp) return arr, num_comp
def heapify(arr, n, i, num_comp): largest = i left = 2i+1 right = 2i+2 if left < n and arr[i] < arr[left]: num_comp += 1 largest = left if right < n and arr[largest] < arr[right]: num_comp += 1 largest = right if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest, num_comp) return num_comp
def heapSort(arr, num_comp): n = len(arr) for i in range(n//2-1, -1, -1): num_comp = heapify(arr, n, i, num_comp) for i in range(n-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] num_comp = heapify(arr, i, 0, num_comp) return arr, num_comp
def findSame(A, B, out): i = 0 j = 0 while i < len(A) and j < len(B): if A[i] < B[j]: i += 1 elif A[i] > B[j]: j += 1 else: out.write("{},".format(A[i])) i += 1 j += 1
def main(): # Step1：从输入文件input.txt中读取集合A和集合B a = np.loadtxt('input.txt', delimiter=',', dtype=int, usecols=(0,)) b = np.loadtxt('input.txt', delimiter=',', dtype=int, usecols=(1,)) # Step2：调用选择