《山东大学《数据结构》实验指导07排序》由会员分享，可在线阅读，更多相关《山东大学《数据结构》实验指导07排序（4页珍藏版）》请在金锄头文库上搜索。
1、实验七 排序一 实验任务常用排序算法的实现。二 实验目的1）掌握常用排序方法的思想，并用C语言实现这些排序算法。2）了解各种常用排序算法的性能（时间复杂性、空间复杂性、算法稳定性、算法简单性等）。三 实验原理1插入排序插入排序有直接插入排序、折半插入排序和希尔排序等方法。直接插入排序类似于线性表中有序表的插入：它由n-1趟排序组成，第i趟排序是向第1到i-1个有序记录之间插入一个新记录，使插入后的记录序列仍为有序。在并向有序表中插入记录时，如果通过“折半查找”来确定插入位置，这就是折半插入排序。希尔排序使用一个序列h1, h2, , ht，叫做增量序列（Increment Sequence）。
2、在使用增量hk的一趟排序之后，对于每一个记录i有PiPi+hk，即所有相隔hk的记录都被排序。此时称该序列是hk-排序（hk-sorted）的。2快速交换排序它的基本思想是，按一定的规则选择某个控制记录作为枢轴（Pivot），首先通过交换各个记录间的位置将它放置在它应该在的位置，使它之前的记录的关键字都比它的关键字小，它之后的记录的关键字都比它的关键字大。对它前后的记录各自形成的子序列，再按同样的规则处理，直到所有记录都被安置在相应的位置上。3选择排序选择排序（Selection Sort）的基本思想是：在对n个记录进行的多趟排序过程中，第i趟排序是在n-i+1个记录中选择关键字最小的记录作为
3、有序序列中的第i个记录，其中，i=1, 2, , n-1。选择排序主要包括简单选择排序和堆排序。简单选择排序（Simple Selection Sort）是一种简单的排序方法。它每次从待排序的记录序列中（范围从i到n）选择出关键字最小的记录，把该记录与序列中的第i个记录交换位置。堆是一个序列，其中每个记录包含一个关键字，序列中的位置k处的关键字，至少大于位置2k和2k+1处（假设这些位置存在于序列中）的关键字。堆排序的过程分为两个步骤。首先，必须重新组合列表中的记录项，使它们满足堆的要求。第二，重复移去堆的顶层，并提升另一个记录项顶替他的位置。4归并排序把两个或多个有序表合并成一个有序表的过程
4、称为归并（Merge）。若归并的有序表有两个，叫做二路归并。对有序表反复利用归并过程进行排序的方法称为归并排序（Merging Sort）。利用二路归并操作的排序称为二路归并排序。二路归并排序的过程是：（1）把无序表中的每一个元素都看作是一个有序表，则有n个有序子表；（2）把n个有序子表按相邻位置分成若干对（若n为奇数，则最后一个子表单独作为一组），每对中的两个子表进行归并，归并后子表数减少一半；（3）反复进行这一过程，直到归并为一个有序表为止。四 实验设备、仪器、工具与资料 微机、VC五 实验内容根据键盘输入的数据建立一个待排序表，利用C语言设计一个主程序完成下列排序运算：1）插入排序（直接
5、插入排序、折半插入排序和Shell排序）2）交换排序（快速排序）3）选择排序（堆排序）4）归并排序5）结束程序运行六 实验步骤（1）实验预习1）预习本实验原理中的各种排序方法的思想。2）分析掌握教材212226页中的算法7-17-10，为完成实验任务做好准备。（2）实验步骤1）问题分析。充分地分析和理解此实验任务，弄清要求作什么，限制条件是什么。2）系统的结构设计。按照以数据结构为中心的原则划分模块。最后写出每个子程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用关系图表示则更加清晰，这样便完成了系统结构设计。3）详细设计。详细设计的目的是对子程序（过程或函数）的进一步求精。用
6、 IF 、WHILE和赋值语句等，以及自然语言写出算法的框架。利用自然语言的目的是避免陷入细节。4）编码。在详细设计的基础上，对详细设计的结果进一步求精，用C语言表示出来。5）在VC环境下调试程序。七 实验报告要求实验报告包含程序开发过程所形成的所有文档资料，包括如下内容：1）需求分析及规格说明：问题描述，求解的问题是什么。2）概要设计：本程序所用的数据类型定义；主程序流程；程序模块及相互关系。3）详细设计：采用C语言定义的数据结构；各模块的伪码算法；各函数调用关系。4）调试报告。5）本实验任务的程序清单及运行结果。八 思考题如何在本试验任务的实现程序中统计出各种排序算法中关键字的比较次数和纪录移动次数？
