基于C语言的多种排序方法的实现 推荐.docx
《基于C语言的多种排序方法的实现 推荐.docx》由会员分享，可在线阅读，更多相关《基于C语言的多种排序方法的实现 推荐.docx（31页珍藏版）》请在冰点文库上搜索。
基于C语言的多种排序方法的实现推荐
基于C语言的多种排序方法的实现
1引言
1.1课题背景
排序问题源远流长，一直是数学地重要组成部分。
随着各种信息的快速更新，排序问题也走进了其他领域以及我们地日常生活。
如何高效地排序一直困扰着我们。
1.2课程设计目的
排序是数学的重要组成部分，工作量大是其存在的问题。
如何高效地排序？
本程序就是解决这个问题而设计。
程序中，把数列储存在数组中，采用插入排序等十种排序方法对数组元素进行排序，高效地解决了排序问题。
本软件开发的平台为最新的微软公司出版的市面最新系统Windows2000，而且可以作为自身的运行平台非常广泛，包括Windows98/2000/XP/Vista等等。
1.3课程设计内容
本程序把对数列的排序转化为对数组元素的排序，用户可以根据自己的实际问题选择系统提供的七种排序方法的任意一种进行排序。
程序通过自身的判断以及处理实现排序。
程序最后输出每趟排序及初始排序结果。
2系统分析与设计方案
2.1系统分析
设计一个排序信息管理系统，使之能够操作实现以下功能：
1）显示需要输入的排序长度及其各个关键字
2）初始化输入的排序序列
3）显示可供选择的操作菜单
4）显示输出操作后的移动次数和比较次数
5）显示操作后的新序列
5）可实现循环继续操
2.2设计思路
通过定义C语言顺序表来存储排序元素信息，构造相关函数，对输入的元素进行相应的处理。
[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]作为监视哨
intlength;//顺序表长度
}SqList;
3.2直接插入排序
直接插入排序是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表
有序序列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]后面，循环以上过程直到最后一个纪录也插入到合理的位置。
整个排序过程是从第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冒泡排序的第一趟比较结果
（1）、将整个的待排序序列的记录序列划分为有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。
（2）、对无序区从前向后依次将相邻记录的数据进行比较，若两结果的大小刚好与排序结果相反，则将其交换，从而始数据值大的记录向右边移动。
计较完无序区的最后两个记录，一趟冒泡排序结束。
无序区最后一个记录进入有序区。
（3）、重复步骤
（2），直到无序区中只剩下一个记录。
3.4快速排序
快速排序是首先选择一个轴值，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键均小于等于轴值，另一部分记录的关键字均大于等于轴值，再分别对这两部分继续进行排序，以达到整个序列有序。
过程描述路下图所示：
初始关键字序列7265788604283734885
ijj
进行1次交换之后48657886042837385
iij
进行2次交换之后48657604283738885
Ijj
进行3次交换之后48657426083734885
Ijj
完成一趟排序4865742607283738885
图3.4一趟快速排序过程
初始状态{7265788604283734885}
一次划分之后{486574260}72{83734885}
分别进行快速排序{426}48{5760}
{6}42
结束
57{60}
结束
{73}83{8885}
结束
{85}88
结束
有序序列{6424857607273838588}
图3.5快速排序的完整过程
3.5堆排序
（1）、用建堆算法建立原始堆；
（2）、堆尾元素与堆顶元素互换；
（3）、再次调用建堆算法建堆；
（4）、重复执行步骤
（2）直到所有元素排好序。
过程描述：
假设，待排序的序列为：
361553184530487293
第一步，建立原始堆结构
36
15
53
18
45
30
48
72
93
36
15
53
18
45
30
48
72
93
a、从第4个节点开始调整b、对第3个节点进行调整
15
36
30
18
45
30
48
72
93
36
15
30
18
45
53
48
72
93
c、对第2个节点进行调整d、连续向下筛选
15
18
30
36
45
53
48
72
93
e、原始堆
图3.6建立原始堆
第二步，15与93交换位置后，重新调整为堆，18为堆顶元素
18
93
18
30
36
45
53
48
72
15
36
30
72
45
53
48
93
15
30
93
图3.7第二次调整
36
48
30
36
53
93
45
72
45
72
48
53
15
18
18
15
图3.8第三次调整
3.6折半插入排序
因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。
如同直接插入排序，只是确定插入的位置时，选择折半查找的方法。
7、简单选择排序
假设排序过程中，待排记录序列的状态为：
无序序列R[i..n]
有序序列R[1..i-1]
图3.9待排序记录序列
排序过程：
第i简单选择排序，从无序序列中选择最小的一个元素，插入到有序序列当中去。
有序序列R[1..i]
无序序列R[i+1..n]
4运行结果
图3.10进行一趟简单选择排序后得序列
4技术难点与分析
4.1将四个子程序串成一个整体
解决方法：
通过编写一个主程序[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（）;
}
}对四个子程序进行调用，始之构成一个整体。
4.2如何对四个子程序的比较和移动次数进行定义
如果都采用整体变量，则在执行过程中会出现数据累加现象，导致计算结果出错，故在定义过程中部分采用整体变量，部分采用局部变量，以此来避免产生冲突。
整体变量执行一次之后的结果如图4.1所示：
图4.1采用整体变量执行一次
整体变量执行二次之后的结果如图4.2所示：
出现数据累加现象
图4.2采用整体变量执行二次
整体和局部变量并用执行两次的结果如图4.3所示，无数据累加情况
图4.3整体和局部变量并用执行两次
5系统测试
5.1系统主界面
图5.1系统主界面
5.2直接插入排序测试
图5.2直接插入排序测试
5.3冒泡排序测试
图5.3冒泡排序测试结果
5.4快速选择排序测试
图5.4快速选择排序测试结果
5.5堆排序测试
图5.5堆排序测试结果
5.6折半插入排序
图5.6折半插入排序测试结果
5.7简单选择排序
图5.7简单选择排序
6结束语
数据结构课程设计和现代计算机技术的实际应用相结合，是我们在本学期学完理论课程之后对自己学习能力的一次很好的检验，从开始的算法思路到运行调试后的可执行程序，都是一个很好的学习和锻炼的过程。
既可以使我们巩固了原有的理论知识，培养了我们灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力，也可以使我们体会到自身知识和能力能在实际中的应用和发挥。
不但可以激发创新意识，还可以开发创造能力、培养沟通能力。
这次数据结构课程设计的时间里虽然时间有限，但确实使我受益非浅。
通过实践课程设计我丰富了编译工具操作经验，更加深了对C语言的了解，熟悉了其环境，更增强了对排序算法的理解与运用。
而且，在完成本课程设计的过程中，也充满磨练了我的意志，锻炼了我的耐心、认真。
在实践的过程中，需要不断的查阅资料，甚至需要求助于老师、同学。
在课程设计中要善于思考，多动手。
我深知，独立完成这样一项任务需要克服许多困难。
总之，数据结构课程设计让我受益良多，我会好好珍惜像这种难得的机会，努力学习知识。
也感谢帮助了我的老师、同学。
参考文献
[1]严蔚敏，吴伟民，数据结构（C语言版）.北京：
清华大学出版社，1997
[2]谭浩强，C程序设计（第三版）.北京：
清华大学出版社，2005
[3]谭浩强，C语言程序设计题解与上机指导（第三版）.北京：
清华大学出版社，2005
[4]JeriR.Hanly，ElliotB.Koffman，问题求解与程序设计C语言版（第四版）.北京：
清华大学出版社，2007-1
[5]何钦铭，颜晖，C语言设计教程.北京:
高等教育出版社，2008年
[6]吴文虎，程序设计基础.北京:
清华大学出版社，2003
附录：
系统源程序代码
#include
#include
#include
#defineMaxSize10//顺序表的最大长度
typedefintKeyType;//定义关键字的类型为整数类型
typedefintInfoType;//定义其他类型为整数类型
intptime=0;
inta=0,b=0,c=0,d=0;//置快速排序和堆排序的移动和比较次数
typedefstruct
{
KeyTypekey;//关键字项
InfoTypeotherinfo;//其他数据项
}RedType;
typedefstruct
{
RedTyper[MaxSize+1];//r[0]作为监视哨
intlength;//顺序表长度
}SqList;
voidprint（SqList*l）
{
inti;
for（i=1;i<=l->length;i++）
printf（"%5d",l->r[i].key）;
printf（"\n"）;
}
//--------------------------------------------------------------------------------------------------------------------------------
//直接插入排序
voidInsertSort（SqList*l,intm,intn）
{//对数组元素r[1]到r[l->length]中的n个元素进行直接插入排序
//r[0]中的内容不作为排序数据，作为一个标记又称为监视哨
inti,j;
for（i=2;i<=l->length;i++）//n-1次循环
{
l->r[0]=l->r[i];//将需要插入的值r[i]赋值给]r[0],设置监视哨
j=i-1;
m++;
while（l->r[0].keyr[j].key&&++n）//查找插入位置
{
l->r[j+1]=l->r[j];//前值覆盖后值
j--;
m++;
}
l->r[j+1]=l->r[0];//将原r[i]中的记录存入第j+1个位置
printf（"第%d趟排序结果为:
",i-1）;
print（l）;
}
printf（"直接插入排序的移动次数为：
%d,比较次数为：
%d\n",m,n）;
}
//--------------------------------------------------------------------------------------------------------------------------------
//冒泡排序
voidBubbleSort（SqList*l,intm,intn）
{
inti,j,k=0;
RedTypetemp;
for（i=l->length;i>1;i--）//n-1趟比较
{
for（j=1;j{
if（l->r[j].key>l->r[j+1].key&&++n）
{
temp=l->r[j];//交换数据
l->r[j]=l->r[j+1];
l->r[j+1]=temp;
m=m+3;
}
}
k++;
printf（"第%d趟排序结果为:
",k）;
print（l）;
}
printf（"冒泡排序的移动次数为：
%d,比较次数为：
%d\n",m,n）;
}
//--------------------------------------------------------------------------------------------------------------------------------
//快速排序
voidQuickSort（SqList*l,intLeft,intRight）
{
inti,j,temp;
i=Left;j=Right;temp=l->r[i].key;//设置初始的排序区
//将i和j分别记录待排序区域的最左侧记录和最右侧记录的位置
while（i{
while（ir[j].key）//从右侧开始扫描
{
j--;
b++;
}//找到第一个小于基准记录的数据
l->r[i]=l->r[j];//覆盖l->r[i]
a++;
while（ir[i].key<=temp）//从右侧开始扫描
{
i++;
b++;}//找到第一个大于基准记录的数据
l->r[j]=l->r[i];//覆盖l->r[j]
a++;
}
l->r[i].key=temp;//找到正确位置
a++;
ptime++;
printf（"第%d次划分排序为:
",ptime）;
print（l）;
if（LeftQuickSort（l,Left,i-1）;//递归调用对左侧分区域再进行快速排序
if（i+1QuickSort（l,i+1,Right）;//递归调用对右侧分区域再进行快速排序
}
//--------------------------------------------------------------------------------------------------------------------------------
//堆排序
//调整l->r[x]的关键字使l->r[x...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;//j为key值较大的记录下标
d++;
if（l->r[0].key>l->r[j].key）
{
d++;
break;
}
l->r[x]=l->r[j];
c++;
x=j;
}
l->r[x]=l->r[0];
c++;
}
//对顺序表l进行堆排序
voidHeapSort（SqList*l）
{
inti,j;
for（i=l->length/2;i>=0;--i）//将l->r[1...i]建成初始堆
HeapAdjust（l,i,l->length）;
printf（"初始序列建成堆：
"）;
print（l）;
for（j=l->length;j>1;--j）//对当前l->r[1...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（x.keyr[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;//置直接插入排序和冒泡排序的移动和比较次数
printf（"\n\n\n"）;
printf（"\t\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"）;
printf（"\t\t#*#*#*#*欢迎进入排序管理系统*#*#*#*#\n"）;
printf（"\t\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"）;
printf（"\n\n\n"）;
printf（"如果碰到意外结束的情况或者排序不正确的情况，请及时联系管理员李立强、\n\n"）;
printf（"本系统为免费系统，如带来任何问题，自己负责、\n\n"）;
printf（"\t\t★☆★☆欢迎使用排序管理系统☆★☆★\n"）;
printf（"\t\t☆请选择所需功能:
☆\n"）;
printf（"\t\t★1.直接插入排序★\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）
{
升级会员 