山东大学《数据结构》实验指导07排序.docx

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