毕业设计_工学_高等教育_教育专区

《毕业设计_工学_高等教育_教育专区》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构中排序方法研究毕业设计班级：计机132姓名：学号：指导教师：孙永林2016-3-18计算机应用（电子商务）广东交通职业技术学院目录内容摘要1引言1正文1一、直接插入排序1二、Shell排序2三、直接选择排序3四、冒泡排序3五、快速排序4六、堆排序4七、基数排序5程序运行结果以及结果分析6对程序结果的评价：7参考文献（或资料）7附录心得7内容摘要数据结构中排序方法研究主耍是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们Z间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机

2、程序设计、数据库、操作系统、编译原理及人工智能等的重要棊础，广泛的应用于信息学、系统工程等各种领域。排序在计算机程序设计中非常重要，各种排序方法各有其优缺点，适用场合也不同。本文从多个方面对各种内排序方法进行全面的比较和分析，最后给出综合结论。关键词：排序方法比较结论引言排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元索的任意序列，重新排列成一个按关键字有序的序列。排序算法是在整个计算机科学与技术领域上广泛被使用的术语。排序算法是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域

3、。排序是计算机科学中最重要的研究问题它在计算机图形、计算机辅助设计、机器人、模式识别及统计学等领域具冇广泛的应用。由于它固冇的理论上的重要性,其功能是将一个数据元素的任意序列重新排列成一个按关键字有序的序列。随着计算机技术的FI益发展，其应用早已不局限于简单的数值运算。阳涉及到问题的分析、数据结构框架的设计以及插入、删除、排序、查找等复杂的非数值处理和操作。排序算法的学习就是为以后利用计算机资源高效地开发II擞值处理的计算机程序打下坚实的理论、方法和技术棊础。正文一、直接插入排序1•原理假设待排序的n个记录｛RO,R1,…，Rn｝顺序存放在数组

4、中，直接插入法在插入记录Ri(i=l,2,…，n・l)时，记录被划分为两个区间［RO,Ri-l］和［Ri+l,Rn・：l］,其中，前一个子区间已经排好序，后一个了区间是当前未排序的部分，将关键码Ki与Ki-lKi-2,…，K0依次比较，找出应该插入的位置，将记录Ri插，然麻将剩下的"个元素按关键词人小依次插入该有序序列,没插入一个元素后依然保持该序列有序，经过"趟排序后即成为有序序列。每次将一•个待排序的记录，按其关键字大小插入到前而已经排好序的子文件中的适当位置，直到全部记录插入完成为止。2.时间复杂度分析肓接插入排序算法必须进行ml趟。最好

5、情况下，即初始序列何序，执行ml趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1),移动元素次数是2(n-l)o因此最好情况下的吋间复朵度就是0(n)o最坏情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复杂度为0(n2)o二、Shell排序1.原理Shell排序又称缩小增量排序‘Shell排序法是以创建者DonaldShell的名字命名的.Shell排序法是对相邻指定距离(称为间隔)的元索进行比较，已知到使用当前间隔进行比较的元索都按顺序排序为止.Shell把间隔缩小一半，然后继续处理，当间隔最终变为1,并且不再出

6、现变化时,Shell排序也就完成了其处理过程.先取一个整数dlvn,把全部记录分成dl个组，所有距离为dl借数的记录放在一组中，先在各组内排序;然后去d2

7、好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元索的相对顺序，但在不同的插入排序过程屮,和同的元素可能在各自的插入排序中移动，最后英稳定性就会被打乱，所以shell排序是不稳定的。所以希尔排序是不稳定的，其时间复杂度为o(n2)o三.直接选择排序1.原理待排序的一组数据元素屮，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩卜•的数据元素当中再找最小的与笫二个位置的数据元素交换，循环到只剩卜-最后一个数据元素为止，依次类推臣到所有记录。笫一趟笫n个记录中找出关键码最小的记录与第n个记录交换：笫二趟，从第二个记录开

8、始的，24个记录屮再选出关键码最小的记录与第二个记录交换；如此，第i趟，则从第i个记录开始的n・i+l个记录中选出关键码最小的记录与第i个记录交换，肓