赞
踩
设计3题目:各种排序算法及性能分析
1、设计3目的
掌握各种内排序算法设计及其执行绝对时间,并对其时间性能进行比较。
2、设计3正文
2.1 实验内容
内容:编写一个程序,随机产生n个1-99的正整数序列,分别采用直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序和二路归并排序算法对其递增排序,求出每种排序方法所需要的绝对时间。
要求:为了便于体现各类排序算法的执行时间差别,要求产生不少于50000个随机数进行测试,同时需要编写测试函数用于测试排序结果是否为递增的。
2.2 实验分析
1.直接插入排序 (insertionSort 函数)这种排序方法通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
在代码中,外层循环遍历所有元素,内层循环将当前元素与已排序部分进行比较,并将大于当前元素的值向后移动,最后将当前元素插入到正确位置。
2.折半插入排序 (binaryInsertionSort 函数)这是直接插入排序的一个变种,它通过二分查找减少比较次数,但移动次数不变。
实现方式是在插入过程中使用二分查找确定插入位置,然后将后续元素向后移动,并将当前元素放到找到的位置。
3.希尔排序 (shellSort 函数)希尔排序是插入排序的一种更高效的改进版本,它通过将原来的一维数组分为多个子序列,分别进行直接插入排序。
代码中通过动态定义间隔gap,并在这些间隔上应用插入排序,直至间隔减小为1,即最后一次执行标准的插入排序。
4.冒泡排序 (bubbleSort 函数)冒泡排序是一种简单的排序算法,它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。
在代码中,使用两层嵌套循环实现,外层控制排序的遍数,内层进行相邻元素的比较和交换。
5.快速排序 (quickSort 函数和)快速排序是一种分而治之的排序算法,它通过选取一个枢纽元素,并围绕它重新排列序列,使得枢纽左侧的所有元素都不大于枢纽,右侧的所有元素都不小于枢纽。
代码中的partition函数用于执行这种划分,而quickSort函数则递归地在枢纽的左右两侧进行快速排序。
6.简单选择排序 (selectionSort 函数)选择排序算法是一种原址比较排序算法,它的工作原理是每次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
代码中通过两层循环实现,外层循环表示当前填充的位置,内层循环负责找到剩余元素中的最小值,并将其放到当前位置。
7.堆排序 (heapSort 函数和)堆排序是利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或大于)它的父节点。
heapify函数确保堆的属性,而heapSort函数则首先构建一个最大堆,然后将堆顶元素(最大值)与序列末尾的元素交换,缩小堆大小并重新调整堆。
8.二路归并排序 (mergeSort 函数)归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。
merge函数用于合并两个已排序的序列,mergeSort函数递归地将序列分成两半,分别对它们进行排序,然后使用merge函数将它们合并起来。
该程序的效果如下图所示。
图3-1 比较算法的流程简图
2.3 实验结果与测试
图3-2 生成随机数
图3-3直接插入排序
图3-4折半插入排序
图3-5希尔排序
图3-6 冒泡排序
图3-7 快速排序所涉及的主要函数
图3-8 简单选择排序
图3-9 堆排序所涉及的主要函数
定义Merge()函数,用于扫描整个数组,代码段如下。
图3-10 二路归并的扫描
图3-11 归并子表
图3-12 直接插入排序计算时间的函数
实验结果如图所示:
图3.13 排序实验结果截图
3、设计3总结
本次课程设计实现了八种经典的排序算法:直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序和二路归并排序。代码通过生成随机数数组,并分别对这些数组使用不同的排序算法进行排序,然后计算每种排序算法所需的时间,并判断排序结果是否为递增序列。
在完成本次课程设计时,我对各种排序算法有了更深入的了解。通过实际编码实现和对比不同算法的性能,我加深了对每种算法的理解,并学会了如何选择合适的排序算法来解决不同的问题。然而,本次代码还存在一些不足之处。首先,代码中使用了大量的全局变量,这会导致代码的可读性和可维护性下降。其次,数组的大小被硬编码为50000,这限制了代码的灵活性,应该考虑使用动态内存分配来处理不同大小的数组。
通过本次课程设计,我学习到了不同的排序算法的原理和实现方式,了解了它们的时间复杂度和空间复杂度。此外,我还学会了如何评估和比较不同排序算法的性能,以及如何选择合适的排序算法来提高程序的效率。在编程思想和方法方面,我体会到了算法设计的重要性。选择合适的算法对问题的解决效率有着巨大的影响,因此在实际开发中需要综合考虑时间复杂度、空间复杂度和实际应用场景等因素,选择最佳的算法。
通过本次课程设计,我还提高了编程能力。实际编码实现了八种排序算法,加深了对C语言的熟悉程度,提升了代码实现和调试的能力。此外,对于算法的理解和分析能力也得到了锻炼和提升。
总之,本次课程设计使我在排序算法方面获得了很多新知识与新技术,深入理解了各种排序算法的原理和实现方式。同时,我也在编程思想和方法、以及编程能力方面得到了提升。这将对我今后的学习和工作有所帮助。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。