《大数据结构课程设计报告材料---几种排序算法地演示(附源代第四次实验码)》由会员分享，可在线阅读，更多相关《大数据结构课程设计报告材料---几种排序算法地演示(附源代第四次实验码)（26页珍藏版）》请在金锄头文库上搜索。
1、word本周的实验主要做快速排序，自己随机生成10000个数据，用快速排序算法，输出排序完成所需时间，再用其他排序方法做比拟，至少完成两个算法的效率比拟数据结构课程设计报告几种排序算法的演示时间：2010-1-14一 需求分析运行环境Microsoft Visual Studio 2005程序所实现的功能对直接插入排序、折半插入排序、冒泡排序、简单项选择择排序、快速排序、堆排序、归并排序算法的演示，并且输出每一趟的排序情况。程序的输入包含输入的数据格式和说明排序种类三输入 排序数的个数的输入 所需排序的所有数的输入 程序的输出程序输出的形式主菜单的输出 每一趟排序的输出，即排序过程的输出二 设
2、计说明算法设计思想交换排序冒泡排序、快速排序交换排序的根本思想是：对排序表中的数据元素按关键字进展两两比拟，如果发生逆序即排列顺序与排序后的次序正好相反，如此两者交换位置，直到所有数据元素都排好序为止。 插入排序直接插入排序、折半插入排序插入排序的根本思想是：每一次设法把一个数据元素插入到已经排序的局部序列的适宜位置，使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列，它只包含一个数据元素。然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序列后，整个排序工作就完成了。 选择排序简单项选择择排序、堆排序选择排序的根本思想是：第一趟在有n个数据元素的排序表中选出关键字
3、最小的数据元素，然后在剩下的n-1个数据元素中再选出关键字最小整个数据表中次小的数据元素，依次重复，每一趟例如第i趟，i=1，n-1总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。等到第n-1趟选择完毕，待排序数据元素仅剩下一个时就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。 归并排序两路归并排序两路归并排序的根本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为1的首尾相接的n个有序子表以后称它们为归并项，先做两两归并，得n/2上取整个长度为2的归并项如果n为奇数，如此最后一个归并项的长度为1
4、；再做两两归并，如此重复，最后得到一个长度为n的有序序列。程序的主要流程图退出系统输出排序结果开始直插折半冒泡选择快排堆排归并选择排序方法进入主菜单程序的主要模块(要求对主要流程图中出现的模块进展说明)程序的主要模块主要分为主菜单模块和排序算法演示模块。 主菜单主要功能：程序运行时，可使运行者根据提醒输入相关操作，从而进入不同的排序方法或者退出。 排序方法与输出 根据运行者对排序的不同选择，进入排序过程a.直接插入排序：根据直接排序的算法，输出排序过程 b.折半插入排序：根据折半插入的算法，输出排序过程 c.冒泡排序：根据冒泡排序算法，输出排序过程 d.简单项选择择排序：根据简单项选择择排序的
5、算法，输出排序过程 e.快速排序：根据快速排序的算法，输出排序过程 f.堆排序：根据堆排序的算法，输出排序过程 g.归并排序：根据归并排序的算法，输出排序过程 程序的主要函数与其伪代码说明 模板类主要说明程序中用到的类的定义templateclass sortlistprivate:int currentsize;/数据表中数据元素的个数public:type *arr;/存储数据元素的向量排序表sortlist():currentsize(0)arr=new typemaxsize;/构造函数sortlist(int n)arr=new typemaxsize;currentsize=n;v
6、oid insert(int i,type x)arri=x;sortlist()delete arr;/析构函数void swap(type &x,type &y)/数据元素x和y交换位置type temp=x;x=y;y=temp;void bubblesort();/冒泡排序void quicksort(int low,int high);/快速排序void insertionsort();/直接插入排序void binaryinsertsort();/折半插入排序void selectsort();/简单项选择择排序void heapsort();/堆排序void mergesort(
7、sortlist &table);/归并排序void filterdown(constint start);/建立最大堆void mergepass(sortlist&sourcetable,sortlist&mergedtable,constint len);/一趟归并void merge(sortlist&sourcetable,sortlist&mergedtable,constint left,constint mid,constint right);/两路归并算法; 直接插入排序直接插入排序的根本思想：开始时把第一个数据元素作为初始的有序序列，然后从第二个数据元素开始依次把数据元素按
8、关键字大小插入到已排序的局部排序表的适当位置。当插入第i(1i=n)个数据元素时，前面的i-1个数据元素已经排好序，这时，用第i个数据元素的关键字与前面的i-1个数据元素的关键字顺序进展比拟，找到插入位置后就将第i个数据元素插入。如此进展n-1次插入，就完成了排序。以下是在顺序表上实现的直接插入排序在顺序表上进展直接插入排序时，当插入第i(1i=n)个数据元素时，前面的arr0、arr1、arri-2已经排好序，这时，用arri-1的关键字依次与arri-2,arri-3,的关键字顺序进展比拟，如果这些数据元素的关键字大于arri-1的关键字，如此将数据元素向后移一个位置，当找到插入位置后就将
9、arri-1插入，就完成了arr0,arr1,arrn-1的排序。伪代码如下template /直接插入排序void sortlist:insertionsort()type temp;int j;for(int i=1;i=0&temparrj) arrj+1=arrj;j-; arrj+1=temp;cout第+num趟排序结果为:;for(int t=0;tcurrentsize;t+) coutarrt ; coutendl;num=0;折半插入排序折半插入排序的根本思想：设在排序表中有n个数据元素arr0,arr1,arrn-1。其中，arr0,arr1,arrn-1是已经排好序的局
10、部数据元素序列，在插入arri时，利用折半查找方法寻找arri的插入位置。折半插入排序方法只能在顺序表存储结构实现。伪代码如下：template /折半插入排序void sortlist:binaryinsertsort()type temp;int left,right;for(int i=1;icurrentsize;i+) left=0;right=i-1;temp=arri;while(left=right)/找插入位置int mid=(left+right)/2;if(temp=left;k-)/向后移动arrk+1=arrk;arrleft=temp;cout第+num趟排序结果为
11、:;for(int t=0;tcurrentsize;t+)coutarrt ;coutendl;num=0; 冒泡排序冒泡排序的根本思想是：设排序表中有n个数据元素。首先对排序表中第一，二个数据元素的关键字arr0和arr1进展比拟。如果前者大于后者，如此进展交换；然后对第二，三个数据做同样的处理；重复此过程直到处理完最后两个相邻的数据元素。我们称之为一趟冒泡，它将关键字最大的元素移到排序表的最后一个位置，其他数据元素一般也都向排序的最终位置移动。然后进展第二趟排序，对排序表中前n-1个元素进展与上述同样的操作，其结果使整个排序表中关键字次大的数据元素被移到arrn-2的位置。如此最多做n-
12、1趟冒泡就能把所有数据元素排好序。伪代码如下：template /冒泡排序void sortlist: bubblesort()int i=1;int finish=0;/0表示还没有排好序while(icurrentsize &!finish)finish=1;/排序完毕标志置为,假定已经排好序for(int j=0;jarrj+1)/逆序swap(arrj,arrj+1);/相邻元素交换位置finish=0;/排序完毕标志置为,表示本趟发生了交换，说明还没有排好序i+;cout第+num趟排序结果为:;for(int t=0;tcurrentsize;t+)coutarrt ;coutendl;num=0;简单项选择择排序直接选择排序直接选择排序的算法根本思想是：a)开始时设i的初始值为0。b)如果in-1，在数据元素序列arriarrn-1中，选出具有最小关键字的数据元素arrk；否如此算法完毕。c)假如arrk不是这组数据元素中的第一个数据元素ik，如此将arrk与arri这两数据元素的位置对调；d)令i=i+1转步骤 b)。伪代码如下：template void sortlist:selectsort()/简单项选择择排序int k;
