《基于C语言的多种排序方法的实现》由会员分享，可在线阅读，更多相关《基于C语言的多种排序方法的实现（31页珍藏版）》请在金锄头文库上搜索。
1、基于C语言的多种排序方法的实现第1页共30页基于C语言的多种排序方法的实现1引言1.1课题背景排序问题源远流长，一直是数学地重要组成部分。随着各种信息的快速更新，排序 问题也走进了其他领域以及我们地日常生活。如何高效地排序一直困扰着我们。1.2课程设计目的排序是数学的重要组成部分，工作量大是其存在的问题。如何高效地排序？本程序 就是解决这个问题而设计。程序中，把数列储存在数组中，采用插入排序等十种排序方 法对数组元素进行排序，高效地解决了排序问题。本软件开发的平台为最新的微软公司 出版的市面最新系统 Windows 2000,而且可以作为自身的运行平台非常广泛，包括 Win dows 98/2
2、000/XP/Vista 等等。1.3课程设计内容本程序把对数列的排序转化为对数组元素的排序， 用户可以根据自己的实际问题选 择系统提供的七种排序方法的任意一种进行排序。 程序通过自身的判断以及处理实现排 序。程序最后输出每趟排序及初始排序结果。2系统分析与设计方案2.1系统分析设计一个排序信息管理系统，使之能够操作实现以下功能：1）显示需要输入的排序长度及其各个关键字2）初始化输入的排序序列3）显示可供选择的操作菜单4）显示输出操作后的移动次数和比较次数5）显示操作后的新序列5）可实现循环继续操2.2设计思路通过定义C语言顺序表来存储排序元素信息，构造相关函数，对输入的元素进行相应的 处理。
3、22.3设计方案设计方案如图2.1所示图2.1设计方案具体流程见图22图2.2 程序流程图3功能设计3.1 SqList 顺序表其中包括顺序表长度，以及顺序表。源代码如下:1typedef structKeyType key;/ 关键字项In foType otheri nfo;其他数据项RedType;typedef structRedType rMaxSize+1;r0作为监视哨int len gth;顺序表长度SqList;3.2直接插入排序直接插入排序是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表有序序列r1,i-1无序系列ri, nJhri有序序列r1 ”
4、 i无序系列ri+1 ” n图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.2513.1513.0212.9212.9513
5、.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冒泡排序的第一趟比较结果(1) 、将整个的待排序序列的记录序列划分为有序区和无序区，初始状态有序区为 空，无序区包括所有待排序的记录。(2) 、对无序区从前向后依次将相邻记录的数据进行比较，若两结果的大小刚好与 排序结果相反，则将其交换，从而始数据值大的记录向右边移动。计较完无序区的 最后两个记录，一趟冒泡排序结束。无序区最后一个记录进入有序区。(3) 、重
6、复步骤(2)，直到无序区中只剩下一个记录。3.4快速排序快速排序是首先选择一个轴值，通过一趟排序将待排记录分割成独立的两部 分，其中一部分记录的关键均小于等于轴值，另一部分记录的关键字均大于等于轴 值，再分别对这两部分继续进行排序，以达到整个序列有序。过程描述路下图所示：初始关键字序列72 6 57 88 60 42 83734885 Lijl j进行1次交换之后657886042837385ij进行2次交换之后48657604283738885进行3次交换之后48657426083734885完成一趟排序4865742607283738885图3.4 趟快速排序过程初始状态7265788一次
7、划分之后4865742分别进行快速排序4264857642结束576042837348856072837348856060结束7383结束8885有序序列642485785结束88607273838588图3.5快速排序的完整过程3.5堆排序（1）、用建堆算法建立原始堆；（2）、堆尾元素与堆顶元素互换；（3）、再次调用建堆算法建堆；（4）、重复执行步骤（2）直到所有元素排好序。过程描述：假设，待排序的序列为：36 15 53 18 45 30 48 72 93第一步，建立原始堆结构C、对第2个节点进行调整、连续向下筛选151830365348459372e、原始堆图3.6建立原始堆933630
8、7245534818151836307253484593151530483672534593181515931830365348457215第二步，15与93交换位置后，重新调整为堆，18为堆顶元素图3.7第二次调整图3.8第三次调整3.6折半插入排序因为R1.i-1是一个按关键字有序的有序序列，则可以利用折半查找实现“在R1.i-1中查找Ri的插入位置”，如此实现的插入排序为折半插入排序。如同直接插解决方法：通过编写一个主程序4入排序，只是确定插入的位置时，选择折半查找的方法。7、简单选择排序假设排序过程中，待排记录序列的状态为：有序序列R1.i-1无序序列 Ri .n图3.9待排序记录序列
9、排序过程：第i简单选择排序，从无序序列中选择最小的一个兀素，插入到有序序列当中去有序序列R1 .i无序序列吉聲i+1 .n图3.10进行一趟简单选择排序后得序列4技术难点与分析4.1将四个子程序串成一个整体void mai n()int i,k;char ch=y;SqList *l;l=(SqList *)malloc(sizeof(SqList);while(ch=y)子程序调用,In sertSort(l, m,n);J JBubbleSort(l,1,l-le ngth);J JQuickSort(l,1,l-le ngth);HeapSort(l);printf(n 是否继续操作(y
10、/n):);getchar();ch=getchar();对四个子程序进行调用，始之构成一个整体4.2如何对四个子程序的比较和移动次数进行定义如果都采用整体变量，则在执行过程中会出现数据累加现象，导致计算结果出错, 故在定义过程中部分采用整体变量，部分采用局部变量，以此来避免产生冲突。整体变量执行一次之后的结果如图 4.1所示:456比较次数为8345图4.1采用整体变量执行一次6 5 44 4 245 6 4 5 2 32363壑rWHM予右犍键犍犍 卡亡-11/总总B frHWPAHH TTX 序录录录录录u果杲果果. 孑己己己己己序/士口士口士口 亠！亠总一茁址-3 2九2 -無为 动录
11、 移记的后 歹己己己己己歹士 口士.口士口韶序序 -个个个个 Ms 12 3 4 LA,卡年卡*“ 入入入入入入始J i - I I - I - I lr - 1 图4.2采用整体变量执行二次222接整体变量执行二次之后的结果如图4.2所示：出现数据累加现象4 6 5 45 6 4 5 2 3为于：；歹nJ nJ己己己歹吉吉吉吉Ms 1 2 3 4 /亍 Ln T* _J r 3 LHiRLAJ-u_ixL_;:lu-MHHHJJJ2比较次数为;34w-Jtl&EBM*aE-丄8一钱犍犍犍* : - - 嵯录录录录杲果果杲.2-: 次为 移记 的后4.3所示，无数据累加情况整体和局部变量并用执行两次的结果如图4 52&525 62456345；仏论较次数为234T 4 4 2 2 lbeji rtlE._ 子二-Jgujj -.叫J dIMTxdTvTIMTx -二:-參己 金桂外矗勺 I期期期勺它i Bb/a-fvnbzMITb/B0 lnFZgr;B0 Fl 一对=茅=甘禄為=1殳芳熹Ff -万己己己己己吉吉吉吉bLtzcL ltEtz八、A“EH312,2333222654比较次数为：8345图4.3整体和局部变量并用执行两次6543入长需直川煨S宋:择选入入入入入入始询磴銅唸接您初更弔
