基于C语言的多种排序方法的实现

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.1所示图2.1设计方

3、案具体流程见图2.2开始图2.2 程序流程图3.1 SqList 顺序表其中包括顺序表长度, typedef structKeyType key;InfoType otherinfo;RedType;typedef struct 3功能设计以及顺序表。源代码如下：1/关键字项/其他数据项RedType rMaxSize+1; int length;SqList;/r0作为监视哨/顺序表长度3.2直接插入排序直接插入排序是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表：图3.1直接插入排序示意图将第i个记录的关键字ri.key顺序地与前面记录的关键字ri-1.key,r

4、i-2.key,r1.key进行比较，把所有关键字大于ri.key的记录依次后移一位，直到关键字小于或 者等于ri.key的记录rj,直接将ri插入到rj后面，循环以上过程直到最后一个纪录 也插入到合理的位置。整个排序过程是从第2个记录开始的，视第1个记录为已经排好序的集合。2.4 冒泡排序冒泡排序是对所有相邻的记录进行比较，若这两个元素刚好与排序结果逆序，则将这两个元素的位置进行交换过程描述如下图所示:图3.2冒泡排序第一趟的前三次比较图3.3冒泡排序的第一趟比较结果(1)、将整个的待排序序列的记录序列划分为有序区和无序区，初始状态有序区为 空，无序区包括所有待排序的记录。(2)、对无序区从

5、前向后依次将相邻记录的数据进行比较，若两结果的大小刚好与 排序结果相反，则将其交换，从而始数据值大的记录向右边移动。计较完无序区的 最后两个记录，一趟冒泡排序结束。无序区最后一个记录进入有序区。(3)、重复步骤(2),直到无序区中只剩下一个记录。2.5 快速排序快速排序是首先选择一个轴值，通过一趟排序将待排记录分割成独立的两部 分，其中一部分记录的关键均小于等于轴值，另一部分记录的关键字均大于等于轴 值，再分别对这两部分继续进行排序，以达到整个序列有序。过程描述路下图所示：初始关键字序列72 6 57 88 60 42 83 734885Ilength); 已子程序调用QuickSort(l,

6、1,l-length);HeapSort(l);printf(n 是否继续操作(y/n):);getchar();ch=getchar();对四个子程序进行调用，始之构成一个整体。4.2 如何对四个子程序的比较和移动次数进行定义如果都采用整体变量，则在执行过程中会出现数据累加现象，导致计算结果出错, 故在定义过程中部分采用整体变量，部分采用局部变量，以此来避免产生冲突。整体变量执行一次之后的结果如图 4.1所示:456比较次数为 8345axlwHM于 6梯擦裤擦dlMIMMfvtK .-多己 勺勺勺勺勺.-灯灯 勺勺1 管录录录录H果果果果募 歹m己己已己歹吉吉士白吉 雪舞盘谦 第1 2 3

7、4-S1/1 /车车入X 入入入入人入始成流瑞福叠- I 1. I - I - I Ir - 一 2*,k 雳为 动录图4.1米用整体变量执行一次整体变量执行二次之后的结果如图4.2所示：出现数据累加现象图4.2采用整体变量执行二次接4 6 5 45 6 4 5 2 32为班趟趟越-4W4BJ4 二 41 A,lA1 A1 A1 AlA Mi刖J前/前 d 剂J5划j 刖府WIMH子6442次为 动录 移记 的后可_习_习_IFV=FV=Fvj身月月月工予 歹己己己已已歹吉士呈口吉一 Ms 1 2 3 4 5 2JE拒咋七; SSS.5S女 12 3 4h LJtl&EB_:he-工a三键键键

8、键:三： 原录录录录果果果悬H 25262562较次K为;344.3所示，无数据累加情况整体和局部变量并用执行两次的结果如图452&52562456345；12,比较次数为234予 QrkhRMT 4 4 2 2 磅机 lbe青_V _ 争二- -,.气 锚镯塘翅镯 力能 .中e-ij/华马 司一哥 -TTTMTrTrvn I* 1I : I* 篆己 勾勾的内时工时灯灯电电i -种=圆1_母_理_|萱”字耳王千 -歹己己己己已歹吉士口吉吉ILL 混臂 翦工 2 3 4 52 EE JjJ- Ek,%/匹入入入入人人始途端3to锄荽523523623563456比较次数为二8345图4.3整体和

9、局部变量并用执行两次直5 6 4 5 2 3 为1 上， .r笈xxrHrH子6 4 4 2 2 性蛆 %一艺二 fh-二？二斗二一4， 一 V JrMmJutjguo -I K桎笆钟叔笆 力声 ”卡占巨巨-辱甘 示宁 力录录录录.果果果果算 歹.-己己己己己歹士口士口士口士 n月回 外由 1 2 3 4 5XZ 丰 Urrl-E %/%4选人入入入入入始谥尚徜相接 ME99盛魅皿刖T Efiv5.1系统王界面5系统测试图5.2直接插入排序测试nmmHwvrwwnmnrvrwnnrwwwvrwwirvrwmwnmmmmrrwwivrwvnmnrwv# *tt*#*# 欢迎进入排序管理系统NF

10、*fl *tt叫果碰到意外结束的情况或者排序不正确的情况，请及时联系管理员李立强、 上系统为免费系统，如带来任何问题，自己负责、统 系, 理能序 序需入晨.ffff璟 -二:r.HF1 -tlH一HH-官 人藁曜-LJ-l-*一 J-LXJ-ErchMEL7 JLU-用SbW速革里出用更选直号快准近团使 LEnF iLj 15请3234567近 a ! I a 123456图5.1系统主界面5.2直接插入排序测试I第3个记录的关键字:：625543643863比较次数为: 7345输入第4个记录的关键字;43Cy/n）：清选择1择蓄第一靠排育W-:多己3 2 为2 : 次加 动录2 6 ;56

11、索 g-Af奏秒初rftKft.， 生司子一方与俳ELEK-;打 簪记记近结结结结监 1-2-棒守二於产%， 选人人人篙霸输5.3冒泡排序测试口 : 泡表；sBOzbE-:欠4P口号列厚喔融舞萼记2-键择摹第选人人入览生3L舞泡.震历22 序蕾锲输：5.4快速选择排序测试2 5 4 3入第3个记录的关键字: 勺： 62554364356221匕较公数为:12输入第4个记录的关键字， 43图5.3冒泡排序测试结果输入第5个记请选择 3键字：输入第4个记录的关键字：输入第5个记5436666图5.4快速选择排序测试结果5.5堆排序测试即fflffi钮*熟录录录录抽媾果果果果明豺 罢臂怏仍(代灌靶嵯

12、慢思韦记 懿IlSBl 选人入入入入入始鬻途逐比奉-2一&L=&=&,二槌键辨辨键MxxrHH子 6e5.6折半插入排序648 374876464336比募屋为463?3438787S781078图5.5堆排序测试结果y/n）：否继续1输入第4个记录的关键字: 43输入第S个记图5.6折半插入排序测试结果5.7简单选择排序请选择；6:-序君福2址由的明为为为为设 貂录录不果果果果胴 募记记而结结结结争 你次抑利河帚第第第第快白二s_ HT选觎第3个记录的关键字工输入第4个记录的关键字：输入第5个记62 S 435435464564564 S 6图5.7简单选择排序6结束语数据结构课程设计和现代

13、计算机技术的实际应用相结合，是我们在本学期学完理论课程之后对自己学习能力的一次很好的检验，从开始的算法思路到运行调试后的可执行程序，都是一个很好的学习和锻炼的过程。既可以使我们巩固了原有的理论知识，培养了我们灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力，也可以使我们体会到自身知识和能力能在实际中的应用和发挥。不但可以激发创新意识，还可以开发创造能力、培养沟通能力。这次数据结构课程设计的时间里虽然时间有限，但确实使我受益非浅。通过实践课程设计我丰富了编译工具操作经验，更加深了对C语言的了解，熟悉了其环境，更增强了对排序算法的理解与运用。而且，在完成本课程设计的过程中，也充满磨练了

14、我的意志，锻炼了我的耐心、认真。在实践的过程中，需要不断的查阅资料，甚至需要求助于老师、同学。在课程设计中要善于思考，多动手。我深知，独立完成这样一项任务需要克服许多困难。总之，数据结构课程设计让我受益良多，我会好好珍惜像这种难得的机会，努力学习知识。也感谢帮助了我的老师、同学。参考文献1严蔚敏，吴伟民，数据结构（C语言版）.北京：清华大学出版社，1997 2谭浩强，C程序设计（第三版）.北京：清华大学出版社，20053谭浩强，C语言程序设计题解与上机指导（第三版）.北京：清华大学出版社，20054 Jeri R.Hanly, Elliot B. Koffman ,问题求解与程序设计 C语言版

15、（第四版）.北京： 清华大学出版社，2007-15何钦铭，颜晖，C语言设计教程.北京：高等教育出版社，2008年6吴文虎，程序设计基础.北京：清华大学出版社，2003录 ：系统源程序代码#include#include#include/顺序表的最大长度/定义关键字的类型为整数类型/定义其他类型为整数类型/置快速排序和堆排序的移动和比较次数/关键字项/其他数据项#define MaxSize 10 typedef int KeyType; typedef int InfoType; int ptime=0;int a=0,b=0,c=0,d=0;typedef structKeyType key

16、;InfoType otherinfo;RedType;typedef structRedType rMaxSize+1;/r0作为监视哨int length;/顺序表长度SqList;void print(SqList *l)int i;for(i=1;ilength;i+)printf(%5d,l-ri.key);printf(n); /直接插入排序 void InsertSort(SqList *l,int m,int n)/对数组元素r1到rl-length中的n个元素进行直接插入排序/r0 中的内容不作为排序数据，作为一个标记又称为监视哨int i,j;for(i=2;ilength

17、;i+)/n-1 次循环l-r0=l-ri;/将需要插入的值ri 赋值给 r0, 设置监视哨j=i-1;m+;while(l-r0.keyrj.key&+n)/查找插入位置l-rj+1=l-rj;/前值覆盖后值j-;m+;l-rj+1=l-r0；将原ri中的记录存入第j+1个位置printf( 第 %d 趟排序结果为:,i-1);print(l);printf(直接插入排序的移动次数为：d,比较次数为：dn,m,n);/冒泡排序void BubbleSort(SqList *l,int m,int n) int i,j,k=0;RedType temp;/n-1 趟比较for(i=l-leng

18、th;i1;i-)for(j=1;jrj.keyl-rj+1.key&+n)temp=l-rj;/交换数据l-rj=l-rj+1;l-rj+1=temp;m=m+3;k+;printf( 第 %d 趟排序结果为:,k);print(l);printf(冒泡排序的移动次数为：d,比较次数为：dn,m,n);/快速排序void QuickSort (SqList *l, int Left,int Right) int i,j,temp;i=Left;j=Right;temp=l-ri.key;/ 设置初始的排序区/将i 和 j 分别记录待排序区域的最左侧记录和最右侧记录的位置while(ij)wh

19、ile (ij&temprj.key) / 从右侧开始扫描j-;b+;/找到第一个小于基准记录的数据l-ri=l-rj;/ 覆盖 l-ria+;while (iri.keyrj=l-ri;/覆盖l-rja+;l-ri.key=temp;/ 找到正确位置a+;ptime+;printf( 第 %d 次划分排序为:,ptime);print(l);if (Lefti-1)QuickSort(l,Left,i-1);/递归调用对左侧分区域再进行快速排序if (i+1rx 的关键字使l-rx.y 成为一个大堆void HeapAdjust(SqList *l, int x,int y)int j;l-

20、r0=l-rx ;for(j=2*x;j=y;j=j*2)if(jrj.keyrj+1.key) +j;/j为key值较大的记录下标 d+;if(l-r0.keyl-rj.key)d+;break;l-rx=l-rj;c+;x=j;l-rx=l-r0;c+;/对顺序表l 进行堆排序void HeapSort(SqList *l)int i,j;/将l-r1.i 建成初始堆/对当前l-r1.i 进行堆排序，共做 n-1for(i=l-length/2;i=0;-i)HeapAdjust(l,i,l-length);printf( 初始序列建成堆：);print(l);for(j=l-length

21、;j1;-j)趟l-r0=l-rj;l-rj=l-r1;l-r1=l-r0;c=c+3;HeapAdjust(l,1,j-1);printf( 第 %d 趟建堆结果为:,l-length-j+1);print(l);void BinSort (SqList *l, int length)/*对记录数组r进行折半插入排序，length为数组的长度*/int i,j;RedType x;int low,high,mid;for ( i=2; i ri;low=1; high=i-1;while (low=high )/* 确定插入位置*/mid=(low+high) / 2;if ( x.key

22、rmid.key )high=mid-1;elselow=mid+1;记录依次向后移动for ( j=i-1 ; j= low; -j )l-rj+1= l-rj;/*/l-rlow=x; /* 插入记录*/printf( 第 %d 趟排序结果为:,i-1);print(l);/*BinSort*/void SelectSort(SqList *l, int length)/*对记录数组r做简单选择排序，length为数组的长度*/int i,j,k;int n;RedType x;n=length;for ( i=1 ; i= n-1; +i)k=i;for ( j=i+1 ; jrj.ke

23、y rk.key )k=j;if ( k!=i)x= l-ri;l-ri= l-rk;l-rk=x;printf( 第 %d 趟排序结果为:,i);print(l); /* SelectSort */void main()int i,k;char ch=y;SqList *1;l=(SqList *)malloc(sizeof(SqList);while(ch=y)(int m=0,n=0; /置直接插入排序和冒泡排序的移动和比较次数 printf(nnn);printf(tt#*#*#*#*欢迎进入排序管理系统 *#*#*#*#n);p p| n tf* *、n ),printf(nnn);

24、printf(如果碰到意外结束的情况或者排序不正确的情况，请及时联系管理员李 立强、nn);printf(本系统为免费系统，如带来任何问题，自己负责、 nn);printf（tt 欢迎使用排序管理系统 n）;printf(tt 请选择所需功能： rT);printf(tt 1.直接插入排序n);printf(tt 2.冒泡排序rT);printf(tt 3.快速排序n);printf(tt 4.堆排序rT);printf(tt 5.折半插入排序rT);printf(tt 6.简单选择排序rT);printf(tt 7.退出系统n);printf(tt 欢迎使用排序管理系统n);printf(n

25、nn);printf(请选择：);scanf(%d,&k);switch (k)case 1:printf(n 您选择的是直接插入排序：n);printf(输入要排序列表的长度n：);scanf(%d,&l-length);for(i=1;ilength;i+)printf( 输入第 %d 个记录的关键字：,i);scanf(%d,&l-ri.key);printf(初始输入序列为：);print(l);InsertSort(l,m,n);printf(直接插入排序后记录为：”)；print(l);break;case 2:printf(n 您选择的是冒泡排序：n);printf(输入要排序列

26、表的长度n：);scanf(%d,&l-length);for(i=1;ilength;i+)printf( 输入第 %d 个记录的关键字：,i);scanf(%d,&l-ri.key);printf(初始输入序列为：);print(l);BubbleSort(l,1,l-length);printf(冒泡排序后记录为：);print(l);break;case 3:printf(n 您选择的是快速排序：n);printf（ 输入要排序列表的长度n： ）;scanf（%d,&l-length）;for（i=1;ilength;i+）printf（ 输入第 %d 个记录的关键字：,i）;scan

27、f（%d,&l-ri.key）;printf（ 初始输入序列为：）;print（l）;QuickSort（l,1,l-length）;printf（快速排序的移动次数为：d,比较次数为：dn,a,b）;printf（ 快速排序后记录为:）;print（l）;break;case 4:printf（n 您选择的是堆排序：n）;printf（ 输入要排序列表的长度n： ）;scanf（%d,&l-length）;for（i=1;ilength;i+）printf（ 输入第 %d 个记录的关键字：,i）;scanf（%d,&l-ri.key）;printf（ 初始输入序列为：）;print（l）;H

28、eapSort（l）;printf（堆排序的移动次数为：d,比较次数为：dn,c,d）;printf（ 堆排序后记录为：）;print（l）;break;case 5:printf（n 您选择的是折半插入排序：n）;printf（ 输入要排序列表的长度n： ）;scanf(%d,&l-length);for(i=1;ilength;i+)printf( 输入第 %d 个记录的关键字：,i);scanf(%d,&l-ri.key);printf( 初始输入序列为：);print(l);BinSort (l,l-length);printf( 快速排序后记录为:);print(l);break;c

29、ase 6:printf(n 您选择的是简单选择排序：n);printf( 输入要排序列表的长度n： );scanf(%d,&l-length);for(i=1;ilength;i+)printf( 输入第 %d 个记录的关键字：,i);scanf(%d,&l-ri.key);printf( 初始输入序列为：);print(l);SelectSort(l, l-length);printf( 快速排序后记录为:);print(l);break;case 7:break;default:printf( 没有找到你需要的排序方法);break;printf(n 是否继续操作(y/n):);getchar();ch=getchar();时间飞逝，大学的学习生活很快就要过去，在这四年的学习生活中，收获了很多，而这些成绩的取得是和一直关心帮助我的人分不开的。首先非常感谢学校开设这个课题，为本人日后从事计算机方面的工作提供了经验，奠定了基础。本次毕业设计大概持续了半年，现在终于到结尾了。本次毕业设计是对我大学四年学习下来最好的 检验。经过这次毕业