数据结构中的排序算法操作论文

《数据结构中的排序算法操作论文》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.大学软件工程硕士数据结构论文论文题目:数据结构中的排序算法操作...数据结构中的排序算法操作摘要：本文通过对数据结构中排序算法深入研究,实现了排序算法中的直接插入排序、快速排序和简单选择排序操作，进一步加深了对数据结构中排序算法的理解，得到的算法可以应用到以后的编程实践中。最后给出了各个算法时间复杂度、空间复杂度和算法稳定性的分析。关键词：排序时间复杂度空间复杂度稳定性TheAlgorithmsofsortingindatastructureAbsract:Thispapergivesadeepexplorationofsortinginda

2、tastructure,implem-entstheStraightinsertion_sortQuick_sortandSimpleselection_sortofit.Thealgorithmwegetcouldbeusedinthelaterprogrammingexperience.Thelastofthepapergivestimecomplexityspacecomplexityandstabilityofeveryalgorithms.Keywords:sortingtimecomplexityspacecomplexitysta

3、bility1.引言排序是日常生活和工作中的一个常见问题，其目的是将一组原本无序的数据元素（或记录）序列，按照人们所需要的顺序，排列成有规律的按关键字有序的序列。在现实生活中，人们要用到排序。如：学生成绩往往需要按照成绩高低或按学号从前到后排序；在图书馆众多的图书中，需要按照各个学科将书籍归类；排队时从高到低的顺序排队等问题。同样，排序也是计算机程序设计中的一个非常重要的操作，在计算机软件设计中占有极其重要的地位。本文将对排序算法中直接插入排序、快速排序和简单选择排序三种算法的实现做一些研究。2.算法的实现2.1数据结构描述...本文研究的待排

4、序的记录采用顺序存储结构，设记录的关键字均为整数。待排序的记录的数据类型为：#defineMAXSIZE20//顺序表最大长度的假定值typedefintKeyType;//不妨设关键字类型为整型typedefstruct{KeyTypekey;//关键字域InfoTypeotherinfo;//其他域}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作监视哨单元intlength;//顺序表长度}SqList;//顺序表类型2.2函数功能的描述假设待排序的记录的关键字序列为：

5、49,38,65,97,76,13,27,49’，排序以后的记录按关键字非递减有序2.2.1直接插入排序的基本思想：每次将待排序的一个记录按其关键字大小插入到已经排好序的子序列中，直到所有的记录都插入完为止。直接插入排序的过程如图2.1所示：[初始关键字]（49）38659776132749’i=2:(38)(3849)659776132749’i=3:(38)(384965)9776132749’i=4:(38)(38496597)76132749’i=5:(76)(3849657697)132749’i=6:(13)(13384965769

6、7)2749’i=7:(27)(13273849657697)49’i=8:(49’)(1327384949’657697)监视哨L.r[0]图2.12.2.2...快速排序的基本思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分的记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序以达到整个序列有序。整个排序过程采用递归方式，一趟快速排序过程如图2.2(a)图所示：pivotkey初始关键字4938659776132749’ijj进行1次移动后27386597761349’iij进行2次移动后273897761

7、36549’ijj进行3次移动后27381397766549’iij进行4次移动后27381376976549’ijj完成一趟排序2738134976976549’图2.2(a)排序的全过程如图2.2(b)所示：初始状态{4938659776132749’}一次划分之后{273813}49{76976549’}分别进行快速排序{13}27{38}结束结束{49’65}76{97}49’{65}结束结束有序序列{1327384949’657697}图2.2(b)2.2.3简单选择排序的基本思想：每一趟在n-i+1(i=1,2,……,n-1)个记录

8、中选取关键字最小的记录作为有序序列中的第i个记录，并和第i(0