《基于c语言的多种排序方法的实现-毕业论文.doc》由会员分享，可在线阅读，更多相关《基于c语言的多种排序方法的实现-毕业论文.doc（31页珍藏版）》请在金锄头文库上搜索。
1、基于C语言的多种排序方法的实现1 引 言1.1 课题背景排序问题源远流长，一直是数学地重要组成部分。随着各种信息的快速更新，排序问题也走进了其他领域以及我们地日常生活。如何高效地排序一直困扰着我们。1.2 课程设计目的排序是数学的重要组成部分，工作量大是其存在的问题。如何高效地排序？本程序就是解决这个问题而设计。程序中，把数列储存在数组中，采用插入排序等十种排序方法对数组元素进行排序，高效地解决了排序问题。本软件开发的平台为最新的微软公司出版的市面最新系统Windows 2000，而且可以作为自身的运行平台非常广泛，包括 Windows 98/2000/XP/Vista等等。1.3课程设计内容
2、本程序把对数列的排序转化为对数组元素的排序，用户可以根据自己的实际问题选择系统提供的七种排序方法的任意一种进行排序。程序通过自身的判断以及处理实现排序。程序最后输出每趟排序及初始排序结果。 2 系统分析与设计方案 2.1 系统分析 设计一个排序信息管理系统，使之能够操作实现以下功能：1) 显示需要输入的排序长度及其各个关键字2) 初始化输入的排序序列3) 显示可供选择的操作菜单4) 显示输出操作后的移动次数和比较次数5) 显示操作后的新序列5) 可实现循环继续操2.2 设计思路通过定义C语言顺序表来存储排序元素信息，构造相关函数，对输入的元素进行相应的处理。 22.3 设计方案设计方案如图2.
3、1所示开始定义顺序表相关函数的声明主函数退出系统图2.1 设计方案具体流程见图2.2开始菜单插入排序冒泡排序快速排序堆排序是否继续操作结束退出排序折半插入排序简单选择排序 输入数据图2.2 程序流程图3功能设计3.1 SqList顺序表其中包括顺序表长度，以及顺序表。源代码如下：1typedef struct KeyType key; /关键字项 InfoType otherinfo; /其他数据项RedType;typedef struct RedType rMaxSize+1; /r0作为监视哨int length; /顺序表长度SqList;3.2 直接插入排序 直接插入排序是将一个记录
4、插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表有序序列r1i-1无序系列rinri有序序列r1i 无序系列ri+1n 图3.1 直接插入排序示意图将第i个记录的关键字ri.key顺序地与前面记录的关键字ri-1.key,ri-2.key,，r1.key进行比较，把所有关键字大于ri.key的记录依次后移一位，直到关键字小于或者等于ri.key的记录rj，直接将ri插入到rj后面，循环以上过程直到最后一个纪录也插入到合理的位置。整个排序过程是从第2个记录开始的，视第1个记录为已经排好序的集合。3.3 冒泡排序 13.25 13.15 13.02 12.92 12.95 13.10
5、交换 冒泡排序是对所有相邻的记录进行比较，若这两个元素刚好与排序结果逆序，则将这两个元素的位置进行交换。 过程描述如下图所示： 13.15 13.25 13.02 12.92 12.95 13.10交换交换 13.15 13.02 13.25 12.92 12.95 13.10图3.2 冒泡排序第一趟的前三次比较 13.15 13.02 12.92 12.95 13.10 13.25图3.3 冒泡排序的第一趟比较结果（1）、将整个的待排序序列的记录序列划分为有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。（2）、对无序区从前向后依次将相邻记录的数据进行比较，若两结果的大小刚好与
6、排序结果相反，则将其交换，从而始数据值大的记录向右边移动。计较完无序区的最后两个记录，一趟冒泡排序结束。无序区最后一个记录进入有序区。（3）、重复步骤（2），直到无序区中只剩下一个记录。3.4 快速排序快速排序是首先选择一个轴值，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键均小于等于轴值，另一部分记录的关键字均大于等于轴值，再分别对这两部分继续进行排序，以达到整个序列有序。 过程描述路下图所示：初始关键字序列 72 6 57 88 60 42 83 73 48 85 i j j 进行1次交换之后 48 6 57 88 60 42 83 73 85 i i j进行2次交换之后
7、48 6 57 60 42 83 73 88 85 I j j进行3次交换之后 48 6 57 42 60 83 73 48 85 I j j完成一趟排序 48 6 57 42 60 72 83 73 88 85图3.4 一趟快速排序过程初始状态 72 6 57 88 60 42 83 73 48 85一次划分之后 48 6 57 42 60 72 83 73 48 85分别进行快速排序 42 6 48 57 60 6 42 结束 57 60 结束 73 83 88 85 结束 85 88 结束有序序列 6 42 48 57 60 72 73 83 85 88图3.5 快速排序的完整过程3.5
8、 堆排序 （1）、用建堆算法建立原始堆；（2）、堆尾元素与堆顶元素互换；（3）、再次调用建堆算法建堆；（4）、重复执行步骤（2）直到所有元素排好序。过程描述：假设，待排序的序列为：36 15 53 18 45 30 48 72 93第一步，建立原始堆结构361553184530487293361553184530487293 a、从第4个节点开始调整 b、对第3个节点进行调整153630184530487293361530184553487293 c、对第2个节点进行调整 d、连续向下筛选151830364553487293e、原始堆 图3.6 建立原始堆第二步，15与93交换位置后，重新调整
9、为堆，18为堆顶元素18931830364553487215363072455348931530 93图3.7 第二次调整36483036539345724572485315181815图3.8 第三次调整3.6 折半插入排序因为 R1.i-1 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R1.i-1中查找Ri的插入位置”，如此实现的插入排序为折半插入排序。如同直接插入排序，只是确定插入的位置时，选择折半查找的方法。7、简单选择排序假设排序过程中，待排记录序列的状态为：无序序列 Ri.n有序序列R1.i-1 图3.9 待排序记录序列排序过程：第i简单选择排序，从无序序列中选择最小的一个元素，插入到有序序列当中去。有序序列R1.i无序序列 Ri+1.n4 运行结果 图3.10 进行一趟简单选择排序后得序列4 技术难点与分析4.1 将四个子程序串成一个整体 解决方法：通过编写一个主程序 4void main()int i,k;char ch=y;SqList *l; l=(SqList *)malloc(s
