李瑜波数据结构中的排序算法操作论文.docVIP

四川大学软件工程硕士 数据结构论文 论文题目: 数据结构中的排序算法操作 姓名：_________李瑜波_____________ 学号：_________________________________ 2012年3月16日 数据结构中的排序算法操作 经济学院 （李瑜波） 摘要：本文通过对数据结构中排序算法深入研究,实现了排序算法中的直接插入排序、快速排序和简单选择排序操作，进一步加深了对数据结构中排序算法的理解，得到的算法可以应用到以后的编程实践中。最后给出了各个算法时间复杂度、空间复杂度和算法稳定性的分析。 关键词：排序 时间复杂度 空间复杂度 稳定性 The Algorithms of sorting in data structure Absract: This paper gives a deep exploration of sorting in data structure, implem- ents the Straight insertion_sort Quick_sort and Simple selection_sort of it. The algorithm we get could be used in the later programming experience. The last of the paper gives time complexity space complexity and stability of every algorithms. Keywords: sorting time complexity space complexity stability 1.引言 排序是日常生活和工作中的一个常见问题，其目的是将一组原本无序的数据元素（或记录）序列，按照人们所需要的顺序，排列成有规律的按关键字有序的序列。 在现实生活中，人们要用到排序。如：学生成绩往往需要按照成绩高低或按学号从前到后排序；在图书馆众多的图书中，需要按照各个学科将书籍归类；排队时从高到低的顺序排队等问题。同样，排序也是计算机程序设计中的一个非常重要的操作，在计算机软件设计中占有极其重要的地位。本文将对排序算法中直接插入排序、快速排序和简单选择排序三种算法的实现做一些研究。 2. 算法的实现 2.1 数据结构描述 本文研究的待排序的记录采用顺序存储结构，设记录的关键字均为整数。待排序的记录的数据类型为： #define MAXSIZE 20 // 顺序表最大长度的假定值 typedef int KeyType; // 不妨设关键字类型为整型 typedef struct { KeyType key; // 关键字域 InfoType otherinfo; // 其他域 }RedType; // 记录类型 typedef struct { RedType r[MAXSIZE+1];//r[0]闲置或用作监视哨单元 int length; // 顺序表长度 }SqList; // 顺序表类型 2.2 函数功能的描述 假设待排序的记录的关键字序列为：49,38,65,97,76,13,27,49’，排序以后的记录按关键字非递减有序 2.2.1 直接插入排序的基本思想：每次将待排序的一个记录按其关键字大小插入到已经排好序的子序列中，直到所有的记录都插入完为止。直接插入排序的过程如图2.1所示： [初始关键字] （49） 38 65 97 76 13 27 49’ i=2: (38) (38 49) 65 97 76 13 27 49’ i=3: (38) (38 49 65) 97 76 13 27 49’ i=4: (38) (38 49 65 97) 76 13 27 49’ i=5: (76) (38 49 65 76 97) 13 27 49’ i=6: (13) (13 38 49 65 76 97) 27 49’ i=7: (27) (13 27 38 49 65 76 97) 49’ i=8: (49’) (13 27 38 49 49’ 65 76 97) 监视哨L.r[0] 图2.1 2.2.2 快速排序的基本思想：通