几种常见的排序算法的实现与性能分析数据结构课程设计报告.doc

. .

课程设计(论文)

题 目名称 几种常见的排序算法的实现与性能分析
课 程 名 称数据构造课程设计
学生XX
学号
系 、专 业 信息工程系、通信工程
指导教师

2012年12月23日
摘 要
设计一个测试程序比较起泡排序、直接排序、简单项选择择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数。运用多种自定义函数，通过在主函数中调用自定义函数，实现其功能，最后输出相应算法的比较次数(至少有五种不同的数据)和移动次数〔关键字的交换记为三次移动〕。从而直观的判断各部排序算法性能的优劣性。
关键词：起泡排序；直接排序；简单项选择择排序；快速排序；希尔排序；堆排序；部排序；直观；比较次数；移动次数

. .word.zl.
. .
目录
1 问题描述1
2 需求分析1
3 概要设计1
3．1抽象数据类型定义1
3．2模块划分2
4 详细设计3
4．1数据类型的定义3
4．2主要模块的算法描述3
5 测试分析8
6 课程设计总结12
参考文献12
附录〔源程序清单〕13

. .word.zl.
. .
1 问题描述
设计一个测试程序比较起泡排序、直接排序、简单项选择择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数以取得直观感受。待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数〔关键字交换记为3次移动〕。最后输出比较结果。
2 需求分析
〔1〕用数组S来存放系统随机产生的100个数据，并放到R数组中，数据由程序随机产生，用户只需查看结果。
〔2〕利用全局变量times和changes来分别统计起泡排序、直接排序、简单项选择择排序、快速排序、希尔排序、堆排序算法的比较次数和移动次数，然后输出结果，并在每一次统计之后，将times和changes都赋值为0。
〔3〕在主函数中调用用户自定义函数，输出比较结果。
〔4〕本程序是对几种部排序算法的关键字进展性能分析的程序，它分为以下几个局部：a、建立数组；b、调用函数求比较和移动次数；c、输出结果。
3 概要设计
3．1抽象数据类型定义
排序数据类型定义：
ADT paixu{
数据对象：D={aij|aij属于{1，2，3…},i,j>0}
数据关系：R={<ai-1,ai>|ai-1,ai∈D，i=2,...,n}
根本操作：
Insertsort();
初始条件：数组已经存在。
根本思想：将一个记录插入到已经排好序的有序列表中，从而得到了一个新的、记录新增1的有序表。
Shellsort();
初始条件：数组已经存在。
根本思想：先取定一个正整数d1<n,把全部记录分成d1个组，所有距离为d1倍数的记录放在一组中，在各组进展插入排序，然后取d2<d1重复上述分组和排序工作，直至取di=1,即所有记录放在一个组中排序为止。
Bubblesort();
初始条件：数组已经存在。
根本思想：两两比较待排序记录的键值，并交换不满足顺序要求的那些偶对，直到全部满足顺序要求为止。
QuickSort(int low,int high)；
初始条件：数组已经存在。
根本思想：在待排序的n个记录中任取一个记录〔通常取第一个记录〕，以该记录的键值为基准用交换的法将所有记录分成两局部，所有键值比它小的安置在一局部，所有键值比它大的安置在另一局部，并把该记录排在两局部的中间，也就是该记录的最终位置。这个过程称为一趟快速排序。然后分别对所划分的两局部重复上述过程，一直重复到每局部只有一个记录为止排序完成。
Selectsort();
初始条件：数组已经存在。
根本思想：每次从待排序的记录中选出键值最小〔或最大〕的记录，顺序放在已排序的记录序列的最后，直到全部排完。对待排序的文件进展n-1趟扫描，第i趟扫描选出剩下的n-i+1个记录，并与第i个记录交换。
Heap();
初始条件：数组已经存在。
根本思想：对一组待排序的的键值，首先是把它们按堆的定义排列成一个序列〔称为初建堆〕，这就找到了最小键值，然后把最小的键值取出，用剩下的键值再重建堆，便得到次小键值，如此反复进展，知道把全部键值排好序为止。
}ADT排序
3．2模块划分
本程序包括两个模块：
〔1〕主程序模块
void main()
{
初始化；
随机数的产生；
调用子函数
}；
〔2〕子函数模块：实现直接插入排序的抽象数据类型。
实现希尔排序的抽象数据类型。
实现冒泡排序的抽象数据类型。
实现快速排序的抽象数据类型。
实现选择排序的抽象数据类型。
实现堆排序的抽象数据类型。
最后输出相应算法的比较次数(至少有五种不同的数据)和移动次数〔关键字的交换记为三次移动〕。从而直观的判断各部排序算法性能的优劣性。
4 详细设计
4．1数据类型的定义
(1)直接插入排序类型：
void Insertsort();
(2)希尔排序类型：
void Shellsort();
(3)冒泡排序类型：
void Bubblesort();
(4)快速排序类型：
void QuickSort(int low,int high);
(5)选择排序类型：
void Selectsort();
(6)堆排序类型：
void Heap();
4．2主要模块的算法描述
下面是主程序的构造图和几个主要模块的流程图：
开场

循环
产生一组随机数

将随机数保存在数组中

堆排序
选择排序
快速排序
起泡排序
希尔
排序
插入排序

记录关键字的比较次数和移动次数

输出关键字的比较次数和移动次数

完毕

4.21主程序构造图
开场

输入要排序的一组元素

i=1,j=1

定义临时中间变量k，并赋初值

i<元素总个数
N
i<i+1

j<元素总个数
NY
j=j+1
第j个元素>第j+1个元素
Y
N
利用k交换第j个元素和第j+1个元素
Y

输出比较次数和移动次数

完毕

4.22冒泡排序关键字比较次数和移动次数的流程图
开场

输入要排序的一组元素

i=1，j=1

定义临时中间变量h，并赋初值

i<元数总个数
N
做第i趟排序
Y

i=i+1
在无序区R[i-n]中选h最小记录R[h]

h记下目前找到的最小关键字所在的位置

交换R[i]和R[h]

输出比较次数和移动次数

完毕

4.23选择排序关键字比较次数和移动次数的流程图
开场

输入要排序的一组元素

定义临时中间变量k，并赋初值

将二叉树转换成堆

i=总元素个数-1

i<=1
N
将堆的根植和最后一个值交换
Y

i--,k++

输出比较次数和移动次数

完毕

4.24堆排序关键字比较次数和移动次数的流程图

5 测试分析

进展了99趟排序后，得到了最终的排序结果，并且也知道了直接插入排序的比较次数和移动次数

了解了直接插入排序的性能后，下面是希尔排序的性能比较：

了解了希尔排序的性能后，下面是冒泡排序的性能比较：

了解了冒泡排序的性能后，下面是快速排序的性能比较：

了解了快速排序的性能后，下面是选择排序的性能比较：

了解了选择排序的性能后，下面是堆排序的性能比较：

以上就是对六种排序算法的一种演示，经过观察和分析我们可以比较六种排序的性能。
6 课程设计总结
通过本次课程设计，我对直接插入排序，希尔排序，选择排序等六种排序的概念有了一个新的认识，也慢慢地体会到了它们之间的微妙。这次的课程设计，加强了我的动手，思考和解决问题的能力。稳固和加深了我对数据构造的理解，也让我懂得了理论与实际相结合是非常重要的，更让我进一步明白了“团结就是力量〞这句话的含义。
在整个设计过程中，构思是很花时间的。调试时经常会遇到这样那样的错误，有的是因为粗心造成的语法错误。当然，很多是因为用错了法，总是实现不了。同时在设计过程中发现了自己的缺乏之处，对以前所学过的知识理解的不够深刻，掌握的不够透彻。
根据我在课程设计中遇到的问题，我将在以后的学习过程中注意以下几点：
1、多在实践中锻炼自己；
2、写程序的过程中要考虑到；
3、在做设计的时候要有信心，有耐心，切勿急躁。
此次的课程设计得以顺利完成，与黄同成教师的耐心指导和同学们的及时帮助是分不开的。当我在编写程序遇到难题时，是黄教师的耐心指导，我才可以突破一个个难关。在程序设计过程中，同学们给我的鼓励和帮助使我信心倍增。在此我再次向黄同成教师和热心帮助我的同学表示深深的意。
参考文献
[1] 黄同成，黄俊民，董建寅．数据构造[M]．：中国电力，2021
[2] 董建寅，黄俊民，黄同成．数据构造实验指导与题解[M]．：中国电力，2021
[3] 蔚敏，伟民. 数据构造〔C语言版〕[M]. ：清华大学，2002
[4] 振鹏，晓莉，郝杰．数据构造[M]．：中国铁道，2003
附录〔源程序清单〕
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define L 100
#define FALSE 0
#define TRUE 1
/*typedef struct
{
int key;
char otherinfo;
}RecType;*/
//typedef RecType Seqlist[L+1];
int s[100],R[100];
int num;
int times=0,changes=0;
//Seqlist R;
void Insertsort();
void Bubblesort();
void QuickSort(int low,int high);
void Shellsort();
void Selectsort();
void Heap();
int Partition();
void main()
{
//Seqlist S;
int i,k;
char ch1,ch2,q;
printf("产生100个随机数：\n");
srand((unsigned)time(NULL));
for(i=1;i<=L;i++)
{
s[i]=rand()%100;
}
for(i=1;i<=L;i++)
{
printf("%4d",s[i]);
}
printf("\n\t排序数据已经输入完毕！");
for(i=1;i<=L;i++)
R[i]=s[i];
ch1='y';
while (ch1=='y'||ch1=='Y')
{
printf("\n\n\n\n\n\t\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* 0--------返 回----------*\n");
printf("\t\t***************************************\n");
printf("\t\t请选择菜单号〔0---6〕:");
scanf("%c",&ch2);getchar();
for(i=1;i<=L;i++)
R[i]=s[i];
switch(ch2)
{
case '1':Insertsort();break;
case '2':Shellsort();break;
case '3':Bubblesort();break;
case '4':
printf("\n\t\t尚未排序的数据为〔回车继续〕：");
for(k=1;k<=L;k++)
printf("%5d",R[k]);
getchar();printf("\n");
num=0;QuickSort(1,L);
break;
case '5':Selectsort();break;
case '6':Heap();break;
case '0':ch1='n';break;
default:printf("\t\t输入错误！请重新输入！\n\t\t");
}
if(ch2!='0')
{
if(ch2=='2'||ch2=='3'||ch2=='4'||ch2=='5'||ch2=='6'||ch2=='7'||ch2=='8')
printf("\n\t排序演示输出完毕！\n");
printf("\n\t请按回车键返回主菜单...");
q=getchar();
if (q!='\xA')
{
getchar();ch1='n';
}
}
}
}
void Insertsort()//直接插入排序
{
int i,j,k,m=0;
printf("\n\t\t尚未排序的数据为〔回车继续〕：");
for(k=1;k<=L;k++)
printf("%5d",R[k]);
getchar();
printf("\n");
for(i=2;i<=L;i++)
{
if(R[i]<R[i-1])
{
R[0]=R[i];j=i-1;
while(R[0]<R[j])
{
times++;
changes++;
R[j+1]=R[j];j--;
}
R[j+1]=R[0];
changes++;
}
m++; times++;
}
printf("\n\n");
printf("\t最终排序结果为：");
for(i=1;i<=L;i++)
printf("%5d",R[i]);
printf("\n");
printf("\n\t直接插入排序的比较次数为%d",times);
printf("\n\t直接插入排序的移动次数为%d",changes);
times=0;
changes=0;
}
void Shellsort() //希尔排序
{
int i,j,gap,x,m=0,k;
printf("\n\t尚未排序的数据为〔回车继续〕：");
for(k=1;k<=L;k++)
printf("%5d",R[k]);
getchar();
printf("\n");
gap=L/2;
while (gap>0)
{
for(i=gap+1;i<=L;i++)
{
j=i-gap;
while(j>0)
{
times++;
if (R[j]>R[j+gap])
{
x=R[j];R[j]=R[j+gap];
R[j+gap]=x;
j=j-gap;
changes++;
}
else
j=0;
}
}
gap=gap/2;
m++;
}
printf("\n\n");
printf("\t最终排序结果为：");
for(i=1;i<=L;i++)
printf("%5d",R[i]);
printf("\n");
printf("\n\t希尔排序的比较次数为%d",times);
printf("\n\t希尔排序的移动次数为%d",changes);
times=0;
changes=0;
}
void Bubblesort()//冒泡排序
{
int i,j,k;
int exchange;
printf("\n\t\t尚未排序的数据为〔回车继续〕：");
for(k=1;k<=L;k++)
printf("%5d",R[k]);
getchar();
printf("\n");
for(i=1;i<=L;i++)
{
exchange=FALSE;
for(j=L;j>=i+1;j--)
{
times++;
if(R[j]<R[j-1])
{
R[0]=R[j];
R[j]=R[j-1];
R[j-1]=R[0];
exchange=TRUE;
changes+=3;
}}
if(exchange);
}
printf("\n\n");
printf("\t最终排序结果为：");
for(i=1;i<=L;i++)
printf("%5d",R[i]);
printf("\n");
printf("\n\t冒泡排序的比较次数为%d",times);
printf("\n\t冒泡排序的移动次数为%d",changes);
times=0;
changes=0;
}
int Partition(int i,int j) //快速排序
{
int pirot=R[i];
while(i<j)
{
while(i<j&&R[j]>=pirot)
{ j--;
times++;
}
if(i<j)
{ R[i++]=R[j];
changes++;
}
while(i<j&&R[i]<=pirot)
{ i++;
times++;
}
if(i<j)
{ R[j--]=R[i];
changes++;
}
}
R[i]=pirot;
return i;
}
void QuickSort(int low,int high)
{
int pirotpos,k,i;
if (low<high)
{
pirotpos=Partition(low,high);
num++;
QuickSort(low,pirotpos-1);
QuickSort(pirotpos+1,high);
}
printf("\n\n");
printf("\t最终排序结果为：\n");
for(i=1;i<=L;i++)
printf("%5d",R[i]);
printf("\n");
printf("\n\t快速排序的比较次数为%d",times);
printf("\n\t快速排序的移动次数为%d",changes);
times=0;
changes=0;
}
void Selectsort() //选择排序
{
int i,j,k,h;
printf("\n\t\t尚未排序的数据为〔回车继续〕：");
for(k=1;k<=L;k++)
printf("%5d",R[k]);
getchar();
printf("\n");
for(i=1;i<=L;i++)
{
h=i;
for(j=i+1;j<=L;j++)
{times++;
if (R[j]<R[h])
h=j;
if(h!=j)
{
R[0]=R[h];R[h]=R[i];R[i]=R[0];
changes+=3;
}
}
}
printf("\n\n");
printf("\t最终排序结果为：");
for(i=1;i<=L;i++)
printf("%5d",R[i]);
printf("\n");
printf("\n\t选择排序的比较次数为%d",times);
printf("\n\t选择排序的比较次数为%d",changes);
times=0;
changes=0;
}
void CreateHeap(int root,int index)//建堆
{
int j,temp,finish;
j=2*root;
temp=R[root];
finish=0;
while (j<=index&&finish==0)
{
if (j<index)
if (R[j]<R[j+1])
{
j++;
times++;
}
if(temp>=R[j])
{
finish=1; //堆建立完成
times++;
}
else
{
R[j/2]=R[j];//父结点=当前结点
j=j*2;
changes++;
}
}
R[j/2]=temp; //父结点=root值
}
void HeapSort()
{
int i,j,temp,k;
for(i=(L/2);i>=1;i--)//将二叉树转换成堆
CreateHeap(i,L);//建堆
for(i=L-1,k=1;i>=1;i--,k++)
{
temp=R[i+1];//堆〔heap〕的root值和最后一个值交换
R[i+1]=R[1];
R[1]=temp;
changes+=3;
CreateHeap(1,i);
}
}
void Heap()
{ int k;
printf("\n\t尚未排序的数据为〔回车继续〕：");
for(k=1;k<=L;k++)
printf("%5d",R[k]);
printf("\n\t");
getchar();
HeapSort();
printf("\n\n");
printf("\t最终排序结果为：");
for(k=1;k<=L;k++)
printf("%5d",R[k]);
printf("\n");
printf("\n\t堆排序的比较次数为%d",times);
printf("\n\t堆排序的移动次数为%d",changes);
times=0;
changes=0;
}

教育之通病是教用脑的人不用手，不教用手的人用脑，所以一无所能。教育革命的对策是手脑联盟，结果是手与脑的力量都可以大到不可思议。

. .word.zl.