Python数据结构与算法-实训指导书7-排序算法 附参考答案

《《Python数据结构与算法》课程实训任务书实训7排序算法【实训目的】应用排序算法：将所学的排序算法应用于实际编程中，提高算法应用能力。性能分析：通过实际运行排序算法，比较不同算法的性能，包括执行速度和资源使用。数据处理：练习从文件读取数据并进行排序，增强数据处理技能。深入理解：通过实践加深对排序算法工作原理的理解。编程技能：提升编程和代码优化技巧。时间复杂度感知：通过实际测量排序时间，直观感受算法的时间复杂度。解决实际问题：通过解决具体问题，如学生成绩排名，增强解决实际问题的能力。代码优化：学习如何优化代码以提高效率和可读性。稳定性认识：了解排序稳定性对结果的影响。自主学习：鼓励自主探索新算法和应用场景。【实训场地】××机房（××实训室）【实训条件】硬件设备：台式电脑，软件设备：Pycharm，word或wps【实训任务】实训任务：学生成绩排名题目描述：你是一名教务处的工作人员，负责管理学生成绩数据。现在你需要编写一个程序，对学生成绩进行排序，并输出排名结果，以便及时了解学生的表现情况。具体要求如下：从文件中读取学生成绩数据，包括学生姓名和对应的成绩。文件内容格式如下：张三,100.00李四,90.5王五,95.32....2.实现至少两种不同的排序算法，并比较它们的性能。3.输出排名前五名的学生姓名和成绩，并输出排序所花费的时间。排序花费时间可以使用time模块的time()方法获取时间戳相减。示例如下：importtimestart_time=time.time()#具体排序操作end_time=time.time()#计算花费时间cost_time=end_time-start_time参考答案：importtime#从文件中读取学生成绩数据defread_grades(filename):grades=[]withopen(filename,'r')asfile:forlineinfile:name,score=line.strip().split(',')grades.append({'name':name,'score':float(score)})returngrades#冒泡排序defbubble_sort_grades(grades):n=len(grades)foriinrange(n):forjinrange(0,n-i-1):ifgrades[j]['score']<grades[j+1]['score']:grades[j],grades[j+1]=grades[j+1],grades[j]returngrades#快速排序defquick_sort_grades(grades):iflen(grades)<=1:returngradespivot=grades[0]left=[xforxingrades[1:]ifx['score']>=pivot['score']]right=[xforxingrades[1:]ifx['score']<pivot['score']]sorted_left=quick_sort_grades(left)sorted_right=quick_sort_grades(right)returnsorted_left+[pivot]+sorted_right#测试代码if__name__=="__main__":filename="scores.txt"grades=read_grades(filename)#冒泡排序start_time=time.time()sorted_grades_bubble=bubble_sort_grades(grades.copy())end_time=time.time()print("冒泡排序:")foriinrange(5):print(f"{i+1}.{sorted_grades_bubble[i]['name']}:{sorted_grades_bubble[i]['score']}")print("冒泡排序花费时间：",end_time-start_time)#快速排序start_time=time.time()sorted_grades_quick=quick_sort_grades(grades.copy())end_time=time.time()print("\n快速排序:")foriinrange(5):print(f"{i+1}.{sorted_grades_quick[i]['name']}:{sorted_grades_quick[i]['score']}")print("快速排序花费时间：",end_time-start_time);【实训注意】×××××（清晰列出本次实训操作的注意点，若有安全方面的注意点，务必重点列出）【拓展任务】拓展任务:希尔排序实现与分析任务描述：步骤1：代码实现希尔排序是插入排序的一种改进版本，它通过比较相隔一定间隔的元素进行交换，从而实现局部排序，最终将间隔逐步减小至1，完成排序过程。请根据7.3.4中的分析，编写Python代码来实现希尔排序算法。参考实现：defshell_sort(arr):n=len(arr)gap=n//2whilegap>0:foriinrange(gap,n):temp=arr[i]j=iwhilej>=gapandarr[j-gap]>temp:arr[j]=arr[j-gap]j-=gaparr[j]=tempgap//=2步骤2：测试测写测试代码，用于验证希尔排序算法的正确性。可以使用一些具有挑战性的测试案例来检验算法的健壮性。比如数据规模大的序列、逆向序列等。参考测试：#编写测试代码，验证希尔排序算法的正确性deftest_shell_sort():arr=[12,34,54,2,3]shell_sort(arr)assertarr==[2,3,12,34,54],"测试成功"arr=[5,4,3,2,1]shell_sort(arr)assertarr==[1,2,3,4,5],"测试成功"#添加更多的测试案例...test_shell_sort()print("测试通过")步骤3：统计交换次数、与插入排序对比。在排序过程中，统计希尔排序的交换次数，并与普通插入排序进行对比。可以采用分析代码的方式，或者是使用代码执行相同的序列进行统计。参考代码defcount_swaps(arr):swaps=0#在排序过程中统计交换次数foriinrange(len(arr)):j=iwhilej>0andarr[j-1]>arr[j]:arr[j-1],arr[j]=arr[j],arr[j-1]swaps+=1j-=1returnswaps#比较希尔排序和插入排序的交换次数arr=[64,34,25,12,22,11,90]swaps_shell_sort=count_swaps(arr.copy())swaps_insertion_sort=count_swaps(arr.copy())print("希尔排序交换次数:",swaps_shell_sort)print("插入排序交换次数:",swaps_insertion_sort)步骤4：分析得出结论根据上述任务实现过程，从时间复杂度、空间复杂度、稳定性、是否原地排序等方面进行算法分析，并与插入排