基于C语言的多种排序方式的实现.docx
《基于C语言的多种排序方式的实现.docx》由会员分享，可在线阅读，更多相关《基于C语言的多种排序方式的实现.docx（27页珍藏版）》请在冰点文库上搜索。
基于C语言的多种排序方式的实现
基于C语言的多种排序方式的实现
1引言
课题背景
排序问题源远流长，一直是数学地重要组成部份。
随着各类信息的快速更新，排序问题也走进了其他领域和咱们地日常生活。
如何高效地排序一直困扰着咱们。
课程设计目的
排序是数学的重要组成部份，工作量大是其存在的问题。
如何高效地排序？
本程序确实是解决那个问题而设计。
程序中，把数列贮存在数组中，采纳插入排序等十种排序方式对数组元素进行排序，高效地解决了排序问题。
本软件开发的平台为最新的微软公司出版的市面最新系统Windows2000，而且能够作为自身的运行平台超级普遍，包括Windows98/2000/XP/Vista等等。
课程设计内容
本程序把对数列的排序转化为对数组元素的排序，用户能够依照自己的实际问题选择系统提供的七种排序方式的任意一种进行排序。
程序通过自身的判定和处置实现排序。
程序最后输出每趟排序及初始排序结果。
2系统分析与设计方案
系统分析
设计一个排序信息治理系统，使之能够操作实现以下功能：
1）显示需要输入的排序长度及其各个关键字
2）初始化输入的排序序列
3）显示可供选择的操作菜单
4）显示输出操作后的移动次数和比较次数
5）显示操作后的新序列
5）可实现循环继续操
设计思路
通过概念C语言顺序表来存储排序元素信息，构造相关函数，对输入的元素进行相应的处置。
[2]
设计方案
设计方案如下图
图设计方案
具体流程见图
图程序流程图
3功能设计
SqList顺序表
其中包括顺序表长度，和顺序表。
源代码如下：
[1]
typedefstruct
{
KeyTypekey;
ey顺序地与前面记录的关键字r[i-1].key,r[i-2].key,……，r[1].key进行比较，把所有关键字大于r[i].key的记录依次后移一名，直到关键字小于或等于r[i].key的记录r[j]，直接将r[i]插入到r[j]后面，循环以上进程直到最后一个纪录也插入到合理的位置。
整个排序进程是从第2个记录开始的，视第1个记录为已经排好序的集合。
冒泡排序
冒泡排序是对所有相邻的记录进行比较，假设这两个元素恰好与排序结果逆序，那么将这两个元素的位置进行互换。
进程描述如以下图所示：
图冒泡排序第一趟的前三次比较
图冒泡排序的第一趟比较结果
（1）、将整个的待排序序列的记录序列划分为有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。
（2）、对无序区之前向后依次将相邻记录的数据进行比较，假设两结果的大小恰好与排序结果相反，那么将其互换，从而始数据值大的记录向右边移动。
计较完无序区的最后两个记录，一趟冒泡排序终止。
无序区最后一个记录进入有序区。
（3）、重复步骤
（2），直到无序区中只剩下一个记录。
快速排序
快速排序是第一选择一个轴值，通过一趟排序将待排记录分割成独立的两部份，其中一部份记录的关键均小于等于轴值，另一部份记录的关键字均大于等于轴值，再别离对这两部份继续进行排序，以达到整个序列有序。
进程描述路以下图所示：
初始关键字序列7265788604283734885
ijj
进行1次互换以后48657886042837385
iij
进行2次互换以后48657604283738885
Ijj
进行3次互换以后48657426083734885
Ijj
完成一趟排序4865742607283738885
图一趟快速排序进程
初始状态{7265788604283734885}
一次划分以后{486574260}72{83734885}
别离进行快速排序{426}48{5760}
{6}42
终止
57{60}
终止
{73}83{8885}
终止
{85}88
终止
有序序列{6424857607273838588}
图快速排序的完整进程
堆排序
（1）、用建堆算法成立原始堆；
（2）、堆尾元素与堆顶元素互换；
（3）、再次挪用建堆算法建堆；
（4）、重复执行步骤
（2）直到所有元素排好序。
进程描述：
假设，待排序的序列为：
361553184530487293
第一步，成立原始堆结构
a、从第4个节点开始调整b、对第3个节点进行调整
c、对第2个节点进行调整d、持续向下挑选
e、原始堆
图成立原始堆
第二步，15与93互换位置后，从头调整为堆，18为堆顶元素
图第二次调整
图第三次调整
折半插入排序
因为R[1..i-1]是一个按关键字有序的有序序列，那么能够利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。
犹如直接插入排序，只是确信插入的位置时，选择折半查找的方式。
7、简单项选择择排序
假设排序进程中，待排记录序列的状态为：
图待排序记录序列
排序进程：
第i简单项选择择排序，从无序序列当选择最小的一个元素，插入到有序序列当中去。
4运行结果
图进行一趟简单项选择择排序后得序列
4技术难点与分析
将四个子程序串成一个整体
解决方式：
通过编写一个主程序[4]
voidmain（）
{
inti,k;
charch='y';
SqList*l;
l=（SqList*）malloc（sizeof（SqList））;
while（ch=='y'）
{……
InsertSort（l,m,n）;
……
BubbleSort（l,1,l->length）;
……子程序挪用
QuickSort（l,1,l->length）;
……
HeapSort（l）;
……
}
printf（"\n是不是继续操作（y/n）:
"）;
getchar（）;
ch=getchar（）;
}
}对四个子程序进行挪用，始之组成一个整体。
如何对四个子程序的比较和移动次数进行概念
若是都采纳整体变量，那么在执行进程中会显现数据累加现象，致使计算结果犯错，故在概念进程中部份采纳整体变量，部份采纳局部变量，以此来幸免产生冲突。
整体变量执行一次以后的结果如下图：
图采纳整体变量执行一次
整体变量执行二次以后的结果如下图：
显现数据累加现象
图采纳整体变量执行二次
整体和局部变量并用执行两次的结果如下图，无数据累加情形
图整体和局部变量并用执行两次
5系统测试
系统主界面
图系统主界面
直接插入排序测试
图直接插入排序测试
冒泡排序测试
图冒泡排序测试结果
快速选择排序测试
图快速选择排序测试结果
堆排序测试
图堆排序测试结果
折半插入排序
图折半插入排序测试结果
简单项选择择排序
图简单项选择择排序
6终止语
数据结构课程设计和现代运算机技术的实际应用相结合，是咱们在本学期学完理论课程以后对自己学习能力的一次专门好的查验，从开始的算法思路到运行调试后的可执行程序，都是一个专门好的学习和锻炼的进程。
既能够使咱们巩固了原有的理论知识，培育了咱们灵活运用和组合集成所学过知识及技术来分析、解决实际问题的能力，也能够使咱们体会到自身知识和能力能在实际中的应用和发挥。
不但能够激发创新意识，还能够开发制造能力、培育沟通能力。
这次数据结构课程设计的时刻里尽管时刻有限，但确实使我受益非浅。
通过实践课程设计我丰硕了编译工具操作体会，加倍深了对C语言的了解，熟悉了其环境，更增强了对排序算法的明白得与运用。
而且，在完本钱课程设计的进程中，也充满考验了我的意志，锻炼了我的耐心、认真。
在实践的进程中，需要不断的查阅资料，乃至需要求助于教师、同窗。
在课程设计中要擅长试探，多动手。
我深知，独立完成如此一项任务需要克服许多困难。
总之，数据结构课程设计让我受益良多，我会好好珍爱像这种宝贵的机遇，尽力学习知识。
也感激帮忙了我的教师、同窗。
参考文献
[1]严蔚敏，吴伟民，数据结构（C语言版）.北京：
清华大学出版社，1997
[2]谭浩强，C程序设计（第三版）.北京：
清华大学出版社，2005
[3]谭浩强，C语言程序设计题解与上机指导（第三版）.北京：
清华大学出版社，2005
[4]Jeri，ElliotB.Koffman，问题求解与程序设计C语言版（第四版）.北京：
清华大学出版社，2007-1
[5]何钦铭，颜晖，C语言设计教程.北京:
高等教育出版社，2020年
[6]吴文虎，程序设计基础.北京:
清华大学出版社，2003
附录：
系统源程序代码
#include<>
#include<>
#include<>
#defineMaxSize10ey）;
printf（"\n"）;
}
eyr[j].key&&++n）ey>l->r[j+1].key&&++n）
{
temp=l->r[j];ey;ey）ey<=temp）ey=temp;.y]成为一个大堆
voidHeapAdjust（SqList*l,intx,inty）
{
intj;
l->r[0]=l->r[x];
for（j=2*x;j<=y;j=j*2）
{
if（jr[j].keyr[j+1].key）
++j;ey>l->r[j].key）
{
d++;
break;
}
l->r[x]=l->r[j];
c++;
x=j;
}
l->r[x]=l->r[0];
c++;
}
.i]建成初始堆
HeapAdjust（l,i,l->length）;
printf（"初始序列建成堆：
"）;
print（l）;
for（j=l->length;j>1;--j）.i]进行堆排序，共做n-1趟
{
l->r[0]=l->r[j];
l->r[j]=l->r[1];
l->r[1]=l->r[0];
c=c+3;
HeapAdjust（l,1,j-1）;
printf（"第%d趟建堆结果为:
",l->length-j+1）;
print（l）;
}
}
voidBinSort（SqList*l,intlength）
/*对记录数组r进行折半插入排序，length为数组的长度*/
{
inti,j;
RedTypex;
intlow,high,mid;
for（i=2;i<=length;++i）
{
x=l->r[i];
low=1;high=i-1;
while（low<=high）/*确信插入位置*/
{
mid=（low+high）/2;
if（r[mid].key）
high=mid-1;
else
low=mid+1;
}
for（j=i-1;j>=low;--j）l->r[j+1]=l->r[j];/*记录依次向后移动*/
l->r[low]=x;/*插入记录*/
printf（"第%d趟排序结果为:
",i-1）;
print（l）;
}
}/*BinSort*/
voidSelectSort（SqList*l,intlength）
/*对记录数组r做简单项选择择排序，length为数组的长度*/
{
inti,j,k;
intn;
RedTypex;
n=length;
for（i=1;i<=n-1;++i）
{
k=i;
for（j=i+1;j<=n;++j）
if（l->r[j].keyr[k].key）
k=j;
if（k!
=i）
{
x=l->r[i];
l->r[i]=l->r[k];
l->r[k]=x;
}
printf（"第%d趟排序结果为:
",i）;
print（l）;
}
}/*SelectSort*/
voidmain（）
{
inti,k;
charch='y';
SqList*l;
l=（SqList*）malloc（sizeof（SqList））;
while（ch=='y'）
{
intm=0,n=0;接插入排序★\n"）;
printf（"\t\t☆2.冒泡排序☆\n"）;
printf（"\t\t★3.快速排序★\n"）;
printf（"\t\t☆4.堆排序☆\n"）;
printf（"\t\t☆5.折半插入排序☆\n"）;
printf（"\t\t☆6.简单项选择择排序☆\n"）;
printf（"\t\t★7.退出系统★\n"）;
printf（"\t\t☆★☆★欢迎利用排序治理系统★☆★☆\n"）;
printf（"\n\n\n"）;
printf（"请选择：
"）;
scanf（"%d",&k）;
switch（k）
{
case1:
printf（"\n您选择的是直接插入排序：
\n"）;
printf（"输入要排序列表的长度n：
"）;
scanf（"%d",&l->length）;
for（i=1;i<=l->length;i++）
{
printf（"输入第%d个记录的关键字：
",i）;
scanf（"%d",&l->r[i].key）;
}
printf（"初始输入序列为：
"）;
print（l）;
InsertSort（l,m,n）;
printf（"直接插入排序跋文录为:
"）;
print（l）;
break;
case2:
printf（"\n您选择的是冒泡排序：
\n"）;
printf（"输入要排序列表的长度n：
"）;
scanf（"%d",&l->length）;
for（i=1;i<=l->length;i++）
{
printf（"输入第%d个记录的关键字：
",i）;
scanf（"%d",&l->r[i].key）;
}
printf（"初始输入序列为：
"）;
print（l）;
BubbleSort（l,1,l->length）;
printf（"冒泡排序跋文录为：
"）;
print（l）;
break;
case3:
printf（"\n您选择的是快速排序：
\n"）;
printf（"输入要排序列表的长度n：
"）;
scanf（"%d",&l->length）;
for（i=1;i<=l->length;i++）
{
printf（"输入第%d个记录的关键字：
",i）;
scanf（"%d",&l->r[i].key）;
}
printf（"初始输入序列为：
"）;
print（l）;
QuickSort（l,1,l->length）;
printf（"快速排序的移动次数为：
%d,比较次数为：
%d\n",a,b）;
printf（"快速排序跋文录为:
"）;
print（l）;
break;
case4:
printf（"\n您选择的是堆排序：
\n"）;
printf（"输入要排序列表的长度n：
"）;
scanf（"%d",&l->length）;
for（i=1;i<=l->length;i++）
{
printf（"输入第%d个记录的关键字：
",i）;
scanf（"%d",&l->r[i].key）;
}
printf（"初始输入序列为：
"）;
print（l）;
HeapSort（l）;
printf（"堆排序的移动次数为：
%d,比较次数为：
%d\n",c,d）;
printf（"堆排序跋文录为：
"）;
print（l）;
break;
case5:
printf（"\n您选择的是折半插入排序：
\n"）;
printf（"输入要排序列表的长度n：
"）;
scanf（"%d",&l->length）;
for（i=1;i<=l->length;i++）
{
printf（"输入第%d个记录的关键字：
",i）;
scanf（"%d",&l->r[i].key）;
}
printf（"初始输入序列为：
"）;
print（l）;
BinSort（l,l->length）;
printf（"快速排序跋文录为:
"）;
print（l）;
break;
case6:
printf（"\n您选择的是简单项选择择排序：
\n"）;
printf（"输入要排序列表的长度n：
"）;
scanf（"%d",&l->length）;
for（i=1;i<=l->length;i++）
{
printf（"输入第%d个记录的关键字：
",i）;
scanf（"%d",&l->r[i].key）;
}
printf（"初始输入序列为：
"）;
print（l）;
SelectSort（l,l->length）;
printf（"快速排序跋文录为:
"）;
print（l）;
break;
case7:
break;
default:
printf（"没有找到你需要的排序方式"）;
break;
}
printf（"\n是不是继续操作（y/n）:
"）;
getchar（）;
ch=getchar（）;
}
}
致谢
时刻飞逝，大学的学习生活专门快就要过去，在这四年的学习生活中，收成了很多，而这些成绩的取得是和一直关切帮忙我的人分不开的。
第一超级感激学校开设那个课题，为本人往后从事运算机方面的工作提供了体会，奠定了基础。
本次毕业设计可能持续了半年，此刻终于到结尾了。
本次毕业设计是对我大学四年学习下来最好的查验。
通过这次毕业设计，我的能力有了专门大的提高，比如操作能力、分析问题的能力、合作精神、严谨的工作作风等方方面面都有专门大的进步。
这期间凝聚了很多人的心血，在此我表示由衷的感激。
没有他们的帮忙，我将无法顺利完成这次设计。
第一，我要专门感激我的明白郭谦功教师对我的悉心指导，在我的论文书写及设计进程中给了我大量的帮忙和指导，为我理清了设计思路和操作方式，并对我所做的课题提出了有效的改良方案。
郭谦功教师渊博的知识、严谨的作风和诲人不倦的态度给我留下了深刻的印象。
从他身上，我学到了许多能受益终生的东西。
再次对周巍教师表示衷心的感激。
第二，我要感激大学四年中所有的任课教师和辅导员在学习期间对我的严格要求，感激他们对我学习上和生活上的帮忙，使我了解了许多专业知识和为人的道理，能够在尔后的生活道路上有继续奋斗的力量。
另外，我还要感激大学四年和我一路走过的同窗朋友对我的关切与支持，与他们一路学习、生活，让我在大学期间生活的很充实，给我留下了很多难忘的回忆。
最后，我要感激我的父母对我的关系和明白得，若是没有他们在我的学习生涯中的无私奉献和默默支持，我将无法顺利完成今天的学业。
致谢
四年的大学生活就快走入尾声，咱们的校园生活就要划上句号，心中是无尽的难舍与爱恋。
从那个地址走出，对我的人一辈子来讲，将是踏上一个新的征程，要把所学的知识应用到实际工作中去。
回顾四年，取得了些许成绩，生活中有欢乐也有艰辛。
感激教师四年来对我孜孜不倦的教诲，对我成长的关切和爱惜。
学友谊深，情同兄妹。
四年的风风雨雨，咱们一同走过，充满着关爱，给我留下了值得收藏的最美好的经历。
在我的十几年求学历程里，离不开父母的鼓舞和支持，是他们辛勤的劳作，无私的付出，为我制造良好的学习条件，我才能顺利完成完成学业，感激他们一直以来对我的抚育与培育。
最后，我要专门感激我的导师刘望蜀教师、和研究生助教吴子仪教师。
是他们在我毕业的最后关头给了咱们庞大的帮忙与鼓舞，给了我很多解决问题的思路，在此表示衷心的感激。
教师们认真负责的工作态度，严谨的治学精神和深厚的理论水平都使我收益匪浅。
他不管在理论上仍是在实践中，都给与我专门大的帮忙，使我取得很多的提高这关于我以后的工作和学习都有一种庞大的帮忙，感激他耐心的辅导。
在论文的撰写进程中教师们给予我专门大的帮忙，帮忙解决了很多的难点，使得论文能够及时完成，那个地址一并表示真诚的感谢。
升级会员 