国开电大《数据结构与算法》形考实验任务2答案（第7章 实验）

PAGE\*MERGEFORMAT3国开电大《数据结构与算法》形考实验任务2答案1.实现冒泡排序算法【实验目的】熟悉并练习冒泡排序算法过程。【实验】一组无序数据序列存储在数组中，对其进行冒泡排序后得到有序数据序列。要求空间复杂度要尽可能低，即尽量少用额外辅助空间。【实验】冒泡排序是不停地比较相邻的记录，如果不满足排序要求（逆序），就交换相邻记录，经过从尾到头（或从头到尾）的一趟扫描后，最小（或最大）的元素就排到了最前面（或最后面）。2.实现直接插入排序算法【实验目的】熟悉并练习直接插入排序算法过程。【实验要求】一组无序数据序列存储在数组中，对其进行直接插入排序后得到有序数据序列。要求空间复杂度要尽可能低，即尽量少用额外辅助空间。【实验分析】直接插入排序是将一个待排序的记录按其关键字的大小插入一个已经排好序的有序序列中合适的位置，在开始时，把第一个记录看成已经排好序的初始有序序列；寻找待插入记录的位置需要进行元素关键字的比较，当比较到比前面关键字大，比后面关键字小的位置，则插入该记录某某分部#实验#学习中心名称班级学生姓名学号课程名称数据结构与算法实验名称实现冒泡排序算法实验目的熟悉并练习冒泡排序算法过程。实验要求一组无序数据序列存储在数组中，对其进行冒泡排序后得到有序数据序列。要求空间复杂度要尽可能低，即尽量少用额外辅助空间。实验内容编程思路、流程与核心代码如下：编程思路：1.获取待排序数组的长度n；2.进入两重循环，外层循环从0到n-1，内层循环从0到n-i-1，对相邻的元素进行比较，如果前一个元素比后一个元素大，则交换两个元素的位置；3.重复以上步骤，直到所有元素有序。流程：1.定义待排序数组arr；2.获取待排序数组的长度n；3.进入两重循环，外层循环从0到n-1，内层循环从0到n-i-1，对相邻的元素进行比较，如果前一个元素比后一个元素大，则交换两个元素的位置；4.返回有序的数组arr。核心代码：以下是Python语言的实现代码：defbubble_sort(arr):"""冒泡排序算法"""n=len(arr)foriinrange(n):forjinrange(0,n-i-1):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]returnarr测试数据与结果（及实验截图）：在测试中，我们将测试数据存储在一个数组中，调用bubble_sort函数进行排序。最后，我们输出有序的数组，可以看到，测试结果符合预期，算法能够正确地将无序的数据序列转换为有序的数据序列。实验体会：在本次实验中，我学习了冒泡排序算法，并且实现了基于Python语言的冒泡排序算法。这个算法通过比较相邻的元素大小，不断将最大的元素移动到数组的末尾，最终实现了数组的排序。通过这个实验，我更加深入地理解了冒泡排序算法的原理和流程。同时，我也学会了如何使用Python语言来实现冒泡排序算法，加深了我的Python编程能力。此外，我还发现冒泡排序算法虽然简单，但在处理大规模数据时效率较低，需要进行优化。通过学习，我了解到其他排序算法（如快速排序、归并排序等）也可以实现对数组的快速排序，可以在一定程度上提高排序的效率。综上所述，这次实验对我来说是一次很好的编程实践，我深入学习了冒泡排序算法，掌握了一种新的排序方法，并学会了如何使用Python语言实现这个算法。教师评语：实验成绩：可增加页数或提供其他附件（如程序代码和截屏图等）某某分部实验报告学习中心名称班级学生姓名学号课程名称数据结构与算法实验名称实现直接插入排序算法实验目的熟悉并练习直接插入排序算法过程。实验要求一组无序数据序列存储在数组中，对其进行直接插入排序后得到有序数据序列。要求空间复杂度要尽可能低，即尽量少用额外辅助空间。实验内容编程思路、流程与核心代码如下：编程思路：1.获取待排序数组的长度n；2.进入一重循环，从1到n-1，将当前元素看作待插入元素key；3.定义一个指针j，从i-1开始向前查找合适的位置，将大于key的元素后移，为key腾出插入位置；4.重复以上步骤，直到所有元素有序。流程：1.定义待排序数组arr；2.获取待排序数组的长度n；3.进入一重循环，从1到n-1，将当前元素看作待插入元素key；4.定义一个指针j，从i-1开始向前查找合适的位置，将大于key的元素后移，为key腾出插入位置；5.返回有序的数组arr。核心代码：definsertion_sort(arr):"""直接插入排序算法"""n=len(arr)foriinrange(1,n):j=i-1key=arr[i]whilej>=0andarr[j]>key:arr[j+1]=arr[j]j-=1arr[j+1]=keyreturnarr测试数据与结果（及实验截图）：在测试中，我们将测试数据存储在一个数组中，调用insertion_sort函数进行排序。最后，我们输出有序的数组，可以看到，测试结果符合预期，算法能够正确地将无序的数据序列转换为有序的数据序列。实验体会：在本次实验中，我学习了直接插入排序算法，并实现了基于Python语言的直接插入排序算法。该算法将无序的数据序列逐个插入已排好序的序列中，通过不断将无序元素插入到合适的位置，最终实现了数据的排序。通过这个实验，我更加深入地理解了直接插入排序算法的原理和流程。同时，我也学会了如何使用Python语言来实现直接插入排序算法，这进一步提高了我的Python编程能力。在实现算法的过程中，我发现直接插入排序算法对于小规模的数据排序效率很高，但对于大规模的数据排序效率较低，需要进行优化。通过学习，我了解到其他排序算法（如快速排序、归并排序等）也可以实现对数组的快速排序，可以在一定程度上提高排序的效率。综上所述，这次实验对我来说是一次很好的编程实践，我深入学习了直接插入排序算法，掌握了一种新的排序方法，并学会了如何使用Python语言实现这个算法。同时，我也对排序算法的性能和优化有了更深入的理解，这对我的编程能力提高和以后的算法实现都会有很大的帮助。教师评语：实验成绩：可增加页数或提供其他附件（如程序代码和截屏图等）