内部排序算法比较.doc

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.37M 资料格式：doc 举报版权申诉

wj199395-5171393-4744300845218921116.doc.pdf-第1页.png

第1页 / 共13页

wj199395-5171393-4744300845218921116.doc.pdf-第2页.png

第2页 / 共13页

wj199395-5171393-4744300845218921116.doc.pdf-第3页.png

第3页 / 共13页

wj199395-5171393-4744300845218921116.doc.pdf-第4页.png

第4页 / 共13页

wj199395-5171393-4744300845218921116.doc.pdf-第5页.png

第5页 / 共13页

wj199395-5171393-4744300845218921116.doc.pdf-第6页.png

第6页 / 共13页

wj199395-5171393-4744300845218921116.doc.pdf-第7页.png

第7页 / 共13页

wj199395-5171393-4744300845218921116.doc.pdf-第8页.png

第8页 / 共13页

文本预览

JLU 数据结构课程设计报告 ——内部排序算法比较

《数据结构》课程设计报告姓名提交日期学号成绩实验室座位号组号指导教师问题解析（对问题的分析、解题思路与解题方法）：利用随机函数产生 N（N>1000）个随机整数，利用起泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序 6 种排序方法进行排序，比较的指标为关键字的比较次数和关键字的移动次数，以取得直观感受，多次试验，同时统计在完全正序、完全逆序情况下的关键字比较次数和移动次数，与无序情况进行对比。解题方法为编写函数，实现： 1）分配内存空间。创建顺序表 2）利用自己编写的函数和伪随机数产生程序产生随机数，作为程序运行的数据 3）实现每种排序算法的功能函数任务分工及进度安排：主程序模块随机数产生模块排序算法模块数据结构选择（包括改进或给出）、算法设计：本程序采用顺序表结构，具体结构定义如下： typedef struct { int key; }ElemType; typedef struct { ElemType *elem; int length; }SqList;

编程与程序清单：头文件和全局变量定义： #include"iostream" #include #include #include"string.h" #include"time.h" using namespace std; #define LIST_INIT_SIZE 50000 Long long int bj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0,n=0; //bj，yd 为记录关键字比较和移动的次数系统共设置16个函数，其中包括主函数。各函数名及功能说明如下。 1） void addlist(SqList &L) 2） void random(SqList &L) //建立个空顺序表 //随机数产生函数 3） void memory(SqList &M,SqList &L) //记录L，以保证每个排序函数使用一组随机数 4） void BubbleSort(SqList &L) //冒泡排序 5） void InsertSort(SqList &L) //直接插入排序 6） void SelectSort(SqList &L) //选择排序 7） int Partition(SqList &L,int low,int high) //返回快速排序枢轴的位置 8） void QSort(SqList &L,int low,int high) //对子序列作快速排序 9） void QuickSort(SqList &L) //对数序表作快速排序 10）void ShellSort (SqList &L) //希尔排序 11）void HeapAdjust(SqList &L,int s,int m )//堆排序算法子程序 12）void HeapSort(SqList &L) //对顺序表进行堆排序 13）void main() //主函数，调用各模块函数 14）void reversed(SqList &L) 15）void order(SqList &L) 16) void compare() //逆序数产生程序 //顺序数产生程序 //输出函数

测试方法、测试数据与测试结果：运行程序后，得到如图所示：

程序的使用说明：（1）采用伪随机数程序产生随机数作为排序的数据。（2）用户只需按提示选择程序功能，并输入随机数个数即可得到结果总结：（对程序进行分析、评价运行效果，总结遇到的问题及解决办法）结果分析：冒泡排序，直接插入排序以及简单选择排序比较次数较多，快速排序，希尔排序及堆排序比较次数较少；并可得冒泡排序和直接插入排序相对较稳定，其他四种内部排序为不稳定排序。在程序产生数为顺序数时，冒泡排序，直接插入排序，简单选择，希尔排序的的性能最好，不需要数据交换，简单选择排序的比较次数最多。在程序产生数为逆序数时，快速排序和堆排序的性能最好，比较次数和交换次数要少很多。总体来说，在产生数据量越来越大的的时候，快速排序，希尔排序及堆排序的性能要远好于其他几种。总体运行良好。出现的问题：开始的时候当多次运行时出现了堆栈溢出的问题，程序会自动关闭，最终找到在 vs2010 中修改堆栈的默认大小的方法，选择项目->属性->链接器->系统->堆栈保留大小,然后输入你想要的栈大小即可。成功解决问题。注：各部分内容要求填写详尽，如空间不够可自行扩充。

附件：程序详细代码： // test1.cpp : 定义控制台应用程序的入口点。 // #include "StdAfx.h" #include"iostream" #include #include #include"string.h" #include"time.h" using namespace std; #define LIST_INIT_SIZE 50000 long long int bj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0,n;//yd，bj 为记录关键字比较和移动的次数 typedef struct { int key; }ElemType; typedef struct { ElemType *elem; int length; }SqList; void addlist(SqList &L)//初始化顺序表 { a: printf("请输入你要输入的个数:"); cin>>n; if(n>50000) printf("超出范围重新输入!!!\n"); goto a; { } } void order(SqList &L)//顺序数产生程序 { L.length=0; for(int i=1;i

void reversed(SqList &L)//逆序数产生程序 { L.length=0; for(int i=1;i30000) goto a; ++L.length; } } void memory(SqList &M,SqList &L)//记录 L，使每个排序算法都用一组相同的随机数 { } M.length=0; for(int i=1;i

bj1++; if(L.elem[i].key>L.elem[i+1].key) {e=L.elem[i].key; L.elem[i].key=L.elem[i+1].key; L.elem[i+1].key=e; yd1+=3; t=i;} } bound=t; } }void InsertSort(SqList &L)//直接插入排序 { int i,j; for(i=2;i<=L.length;i++) { bj2++; if(L.elem[i].key

分享到：

赞收藏

资料库

内部排序算法比较.doc

相关推荐

课程资源

热门标签

最新资料