多种排序方法的实现_以及各种方法之间的比较

《多种排序方法的实现_以及各种方法之间的比较》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1引言1.1课题背景排序问题源远流长，一直是数学地重要组成部分。随着各种信息的快速更新，排序问题也走进了其他领域以及我们地日常生活。如何高效地排序一直困扰着我们。1.2课程设计目的排序是数学的重要组成部分，工作量大是其存在的问题。如何高效地排序？本程序就是解决这个问题而设计。程序中，把数列储存在数组中，采用插入排序等十种排序方法对数组元素进行排序，高效地解决了排序问题。本软件开发的平台为最新的微软公司出版的市面最新系统Windows2000，而且可以作为自身的运行平台非常广泛，包括Windows98/2000/XP/Vista等等。1.3课

2、程设计内容本程序把对数列的排序转化为对数组元素的排序，用户可以根据自己的实际问题选择系统提供的七种排序方法的任意一种进行排序。程序通过自身的判断以及处理实现排序。程序最后输出每趟排序及初始排序结果。2系统分析与设计方案2.1系统分析设计一个排序信息管理系统，使之能够操作实现以下功能：1)显示需要输入的排序长度及其各个关键字2)初始化输入的排序序列3)显示可供选择的操作菜单4)显示输出操作后的移动次数和比较次数5)显示操作后的新序列5)可实现循环继续操2.2设计思路通过定义C语言顺序表来存储排序元素信息，构造相关函数，对输入的元素进行相应的处

3、理。[2]2.3设计方案设计方案如图2.1所示开始定义顺序表相关函数的声明主函数退出系统图2.1设计方案具体流程见图2.2开始菜单插入排序冒泡排序快速排序堆排序是否继续操作结束退出排序折半插入排序简单选择排序输入数据图2.2程序流程图3功能设计3.1SqList顺序表其中包括顺序表长度，以及顺序表。源代码如下：[1]typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其他数据项}RedType;typedefstruct{RedTyper[MaxSize+1];//r[0]作为监视哨intl

4、ength;//顺序表长度}SqList;3.2直接插入排序直接插入排序是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表有序序列r[1……i-1]无序系列r[i……n]r[i]有序序列r[1……i]无序系列r[i+1……n]图3.1直接插入排序示意图将第i个记录的关键字r[i].key顺序地与前面记录的关键字r[i-1].key,r[i-2].key,……，r[1].key进行比较，把所有关键字大于r[i].key的记录依次后移一位，直到关键字小于或者等于r[i].key的记录r[j]，直接将r[i]插入到r[j]

5、后面，循环以上过程直到最后一个纪录也插入到合理的位置。整个排序过程是从第2个记录开始的，视第1个记录为已经排好序的集合。3.3冒泡排序13.2513.1513.0212.9212.9513.10交换冒泡排序是对所有相邻的记录进行比较，若这两个元素刚好与排序结果逆序，则将这两个元素的位置进行交换。过程描述如下图所示：13.1513.2513.0212.9212.9513.10交换交换13.1513.0213.2512.9212.9513.10图3.2冒泡排序第一趟的前三次比较13.1513.0212.9212.9513.1013.25图3.3

6、冒泡排序的第一趟比较结果（1）、将整个的待排序序列的记录序列划分为有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。（2）、对无序区从前向后依次将相邻记录的数据进行比较，若两结果的大小刚好与排序结果相反，则将其交换，从而始数据值大的记录向右边移动。计较完无序区的最后两个记录，一趟冒泡排序结束。无序区最后一个记录进入有序区。（3）、重复步骤（2），直到无序区中只剩下一个记录。3.4快速排序快速排序是首先选择一个轴值，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键均小于等于轴值，另一部分记录的关键字均大于等于轴值，

7、再分别对这两部分继续进行排序，以达到整个序列有序。过程描述路下图所示：初始关键字序列7265788604283734885ijj进行1次交换之后48657886042837385iij进行2次交换之后48657604283738885Ijj进行3次交换之后48657426083734885Ijj完成一趟排序4865742607283738885图3.4一趟快速排序过程初始状态{7265788604283734885}一次划分之后{486574260}72{83734885}分别进行快速排序{426}48{5760}{6}42结束57{60}

8、结束{73}83{8885}结束{85}88结束有序序列{6424857607273838588}图3.5快速排序的完整过程3.5堆排序（1）、用建堆算法建立原始堆；（2）、堆尾