数据结构课程设计—综合排序.doc

东华理工大学

东华理工大学
课程设计报告

课程设计题目： 综合排序的设计

学生姓名：何杨
班 级：1223202
专 业：信息与计算科学
指导教师：郭树蕻

2014年 12 月 13 日

目录

摘要 2
一、题目的内容及要求-------------------------------------------------------------------------------4
二、需求分析--------------------------------------------------------------------------------------------4
三、概要设计--------------------------------------------------------------------------------------------5
四、四种排序源代码详细设计----------------------------------------------------------------------5
五、程序输出的结果---------------------------------------------------------------------------------10
六、运行结果及分析---------------------------------------------------------------------------------12
七、收获及体会---------------------------------------------------------------------------------------13
八、参考文献-------------------------------------------------------------------------------------------14

摘 要
数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，其中包含冒泡排序，直接插入排序，简单选择排序，希尔排序，快速排序，堆排序等，各有其特点。对排序算法比较的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。

关键字：数据结构；算法比较；比较次数；时间复杂度

一、题目的内容及要求
排序综合
利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。
要求：
(1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。
(2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。
(3)如果采用4种或4种以上的方法者，可适当加分。

二、需求分析
2.1 问题描述
此次的任务要求是输入20000个以上的随机整数，对这些数进行多种方法进行排序。（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。 约束：程序可由用户自行设定排序数的个数，但排序数具体值需要由计算机生成，然后用三种以上的排序方法对随机数组进行排序，每一种排序方法执行后需统计出数据移动次数以判断排序方法的对比随机数组的执行优劣性。另：用户自行算出每一种排序方法的时间复杂度与空间复杂度。

2.2 基本要求
2.2.1输入的形式和输入值的范围；
设定的随机数据的范围为20000以上，用户自定义随机数的个数n，随机数的数据类型均为整形。
2.2.2输出的形式；
程序是以一个完整的有序数组来进行输出。
2.2.3程序所达到的功能：
将一个无序数组进行排序随机生成20000以上个随机整数，对这些数进行多种方法进行排序。分别采用以下方法实现上述问题求解（可采用的方法有简单排序、希尔排序、冒泡排序、快速排序这四种排序方法）。

三、概要设计

3.1可排序表的抽象数据类型定义：
typedef int KeyType; //关键字为整型
typedef int OtherType; //关键字为整型

typedef struct
{
KeyType key; //关键字为KeyType型
OtherType other_data;
}RecordType; //定义一个RecordType型结构体，存放关键字
void quicksort(RecordType a[],int left,int right)//快速排序
void bubbleSort(RecordType a[],int length)//冒泡排序
void shellSort(RecordType a[],int n)//希尔排序
void BinSort (RecordType r[], int length)//折半插入排序
void main()//主函数运行入口

四、四种排序源代码详细设计：
4.1快速排序模块：
void quicksort(RecordType a[],int left,int right)
{
RecordType t;
int i,j,temp;
if(left>right)
return;

temp=a[left].key;
i=left;
j=right;
while(i!=j)
{
while(a[j].key>=temp && i<j)
j--;
while(a[i].key<=temp && i<j)
i++;

if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
a[left] = a[i];
a[i].key = temp;

quicksort(a,left,i-1);//继续处理左边的，这是一个递归的过程
quicksort(a,i+1,right);//继续处理右边的，这是一个递归的过程
} /* 快速排序算法 */

4.2冒泡排序模块：
//此处是一次冒泡排序过程，在主函数中会通过循环调用此冒泡函数过程
void bubbleSort(RecordType a[],int length)
{
int i,temp;
for(i=1;i<length;i++)
{
if(a[i].key>a[i+1].key)
{
temp = a[i].key;
a[i].key=a[i+1].key;
a[i+1].key=temp;
}
}
}/* 冒泡排序算法 */

4.3希尔排序模块：
void shellSort(RecordType a[],int n)
{
int i, j, temp;
int gap = 0;
while (gap<=n)//根据待排序的个数生成合适的步长，gap是步长
{
gap = gap * 3 + 1;
}
while (gap > 0)
{
for ( i = gap; i < n; i++ )
{
j = i - gap;
temp = a[i+1].key;
while (( j >= 0 ) && ( a[j+1].key > temp ))
{
a[j + gap+1].key = a[j+1].key;
j = j - gap;
}
a[j+gap+1].key = temp;
}
gap = ( gap - 1 ) / 3;
}
}

4.4希尔折半插入排序模块：
/*折半插入排序法*/
void BinSort (RecordType r[], int length)
/*对记录数组r进行折半插入排序，length为数组的长度*/
{
int i,j;
RecordType x;
int low,high,mid;
for ( i=2; i<=length ; ++i )
{
x= r[i];
low=1; high=i-1;
while (low<=high ) /* 确定插入位置*/
{
mid=(low+high) / 2;
if ( x.key< r[mid].key )
high=mid-1;
else
low=mid+1;
}
for ( j=i-1 ; j>= low; --j ) r[j+1]= r[j]; /* 记录依次向后移动 */
r[low]=x; /* 插入记录 */
}
}/*BinSort*/

4.5主函数模块：
void main()
{
int n,i,j,t;
char b;
bool q=false;
RecordType a[40000];

while(1)
{
printf("\n\n");
printf(" ************** 综 合 排 序*****************************\n\n");
printf(" *********************菜 单***************************\n\n");
printf(" * ======================================================= * \n");
printf(" * 1. 读 取 待排序长度 * \n");
printf(" * 2. 产生随机数并输出 * \n");
printf(" * 3. 采用快速排序法排序 * \n");
printf(" * 4. 采用冒泡排序法排序 * \n");
printf(" * 5. 采用希尔排序法排序 * \n");
printf(" * 6. 采用折半插入排序法排序 * \n");
printf(" * 7. 输 出 * \n");
printf(" * 0. 退 出 系 统 * \n");
printf(" * ------------------------------------------------------- * \n");
printf(" 请输入你要进行的操作");
b = getch();
switch(b)
{
case '1':
printf("%c\n",b);
printf("请输入待排序记录的长度：");
scanf("%d",&n);break;
case '2':
printf("%c\n",b);
srand( (unsigned)time( NULL ));
printf("下面随机生成%d个数字存储在数组中\n",n);
for(i=1;i<=n;i++)
{
a[i].key = rand()%20000;
printf("%d\t",a[i].key);
if(i%100==0)
printf("\n");
}
printf("\n");
break;
case '3':
printf("%c\n",b);
printf("\n -----------------快速排序结束------------------- \n\n");
quicksort(a,1,n);
q=true;break;
case '4':
printf("%c\n",b);
for(i=0;i<n-1;i++)
{
bubbleSort(a,n-i);
}
printf("\n -----------------冒泡排序结束------------------- \n\n");

q=true;break;
case '5':
printf("%c\n",b);
printf("\n -----------------希尔排序结束------------------- \n\n");
shellSort(a,n);
q=true;break;
case '6':
printf("%c\n",b);
BinSort(a,n);
printf("\n -----------------折半插入排序结束------------------- \n\n");

q=true;break;
case '7':
printf("%c\n",b);
if(q)
{
printf("\n -----------------排序后输出------------------- \n");
for(i=1;i<=n;i++)
{
printf("%d\t",a[i].key);
if(i%100==0)
printf("\n");
}
}
else
{
printf("\n * ======================================================= * \n");
printf(" * 您未对待排序数据排序 * \n");
printf(" * 请重新选择排序的序号 * \n");
printf(" * ------------------------------------------------------- * \n");
}
break;
case '0':
printf("%c\n",b);
printf("\n 感谢使用综合排序程序\n 按任意键退出......\n");
return;break;
default:printf("输入错误请重新输入\n\n");
}
}
}

五、程序输出的结果：
5.1输入和输出：
(1)主函数运行的输出结果：

(2)选择1，读取待排序长度（这里以20000为例）：

(3)选择2，产生随机数并输出：

(4)选择3，采用快速排序法排序：

（选择4、5、6的其他排序法的输出雷同，此处就不再重复）
(5)选择7，输出排序结果：

六、运行结果及分析
6.1各算法的比较方法
1.稳定性比较
折半插入排序、冒泡排序是稳定的
希尔排序、快速排序是不稳定的
2.时间复杂性比较
折半插入排序、冒泡排序的时间复杂性为O(n2)
其它非线形排序的时间复杂性为O(nlog2n)
3.辅助空间的比较
线形排序的辅助空间为O(n),其它排序的辅助空间为O(1);
4.其它比较
插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。
反而在这种情况下，快速排序反而慢了。
当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。
当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。

七、收获及体会
根据四种排序法的基础理论实际性模仿和编写算法程序，很是困难，算法是程序的灵魂，数据结构确是算法的基础，但是不断的实践也是一种进步的好途径。这次课程设计主要是对基础知识的灵活应用，这就让我进一步提高了对数结构知识的巩固。这次设计的完成，困难是少不了的，还有很多其它的难题让我都不知道所措，但是通过努力最终解决他们让我体会到成就感，更重要的是我的能力在实践中得到了提升和优化，特别是对常用的排序算法的应用，这对我以后从事软件应用程序开发是有很大的帮助的。这次课程设计的心得体会通过实习我的收获如下1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点： 1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。我通过课程设计建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验，树立团队协作精神。同时，充分弥补了课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助从全局角度把握课程体系，并且可以将理论与实际联系。在课程设计的过程中不仅仅是书本上的知识，这便促使我去查阅更多的课外资料来充实自己的内容，同时学会在面对困难时要耐心得分析它细心得解决它以及通过合作更完美得深入了解剖析它以便得到提高。细心、耐心、团结、求知，是我这次课程设计最大的收获。同时要感谢老师这几天的悉心教导。

八、参考文献

[1] 啊哈磊，《啊哈！算法》，人民邮电出版社，2014-6-1
[2] 刘艳飞，《C语言范例开发大全》清华大学出版社，2010
[3] 严蔚敏，吴伟民。数据结构。北京：清华大学出版社，2001

14