《数据结构课程设计报告---几种排序算法的演示(附源代码)(共48页).doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告---几种排序算法的演示(附源代码)(共48页).doc（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上数据结构课程设计报告 几种排序算法的演示 时间：2010-1-14一 需求分析运行环境Microsoft Visual Studio 2005程序所实现的功能对直接插入排序、折半插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序算法的演示，并且输出每一趟的排序情况。程序的输入（包含输入的数据格式和说明）排序种类三输入 排序数的个数的输入 所需排序的所有数的输入 程序的输出（程序输出的形式）主菜单的输出 每一趟排序的输出，即排序过程的输出二 设计说明算法设计思想交换排序（冒泡排序、快速排序）交换排序的基本思想是：对排序表中的数据元素按关键字进行两两比较，如果发
2、生逆序（即排列顺序与排序后的次序正好相反），则两者交换位置，直到所有数据元素都排好序为止。 插入排序（直接插入排序、折半插入排序）插入排序的基本思想是：每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列，它只包含一个数据元素。然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序列后，整个排序工作就完成了。 选择排序（简单选择排序、堆排序）选择排序的基本思想是：第一趟在有n个数据元素的排序表中选出关键字最小的数据元素，然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素，依次重复，每一
3、趟（例如第i趟，i=1，n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。等到第n-1趟选择结束，待排序数据元素仅剩下一个时就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。 归并排序（两路归并排序）两路归并排序的基本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为1的首尾相接的n个有序子表（以后称它们为归并项），先做两两归并，得n/2上取整个长度为2的归并项（如果n为奇数，则最后一个归并项的长度为1）；再做两两归并，如此重复，最后得到一个长度为n的有序序列。程序的主要流程图退出系统输出排序
4、结果开始直插折半冒泡选择快排堆排归并选择排序方法进入主菜单程序的主要模块(要求对主要流程图中出现的模块进行说明)程序的主要模块主要分为主菜单模块和排序算法演示模块。 主菜单主要功能：程序运行时，可使运行者根据提醒输入相关操作，从而进入不同的排序方法或者退出。 排序方法及输出 根据运行者对排序的不同选择，进入排序过程 a.直接插入排序：根据直接排序的算法，输出排序过程 b.折半插入排序：根据折半插入的算法，输出排序过程 c.冒泡排序：根据冒泡排序算法，输出排序过程 d.简单选择排序：根据简单选择排序的算法，输出排序过程 e.快速排序：根据快速排序的算法，输出排序过程 f.堆排序：根据堆排序的算法
5、，输出排序过程 g.归并排序：根据归并排序的算法，输出排序过程 程序的主要函数及其伪代码说明 模板类主要说明程序中用到的类的定义templateclass sortlistprivate:int currentsize;/数据表中数据元素的个数public:type *arr;/存储数据元素的向量（排序表）sortlist():currentsize(0)arr=new typemaxsize;/构造函数sortlist(int n)arr=new typemaxsize;currentsize=n;void insert(int i,type x)arri=x;sortlist()delet
6、e 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(sortlist &table);/归并排序 void filterdown(co
7、nst int start);/建立最大堆 void mergepass(sortlist&sourcetable,sortlist&mergedtable,const int len);/一趟归并 void merge(sortlist&sourcetable,sortlist&mergedtable,const int left,const int mid,const int right);/两路归并算法; 直接插入排序直接插入排序的基本思想：开始时把第一个数据元素作为初始的有序序列，然后从第二个数据元素开始依次把数据元素按关键字大小插入到已排序的部分排序表的适当位置。当插入第i(1i=n
8、)个数据元素时，前面的i-1个数据元素已经排好序，这时，用第i个数据元素的关键字与前面的i-1个数据元素的关键字顺序进行比较，找到插入位置后就将第i个数据元素插入。如此进行n-1次插入，就完成了排序。以下是在顺序表上实现的直接插入排序在顺序表上进行直接插入排序时，当插入第i(1i=n)个数据元素时，前面的arr0、arr1、arri-2已经排好序，这时，用arri-1的关键字依次与arri-2,arri-3,的关键字顺序进行比较，如果这些数据元素的关键字大于arri-1的关键字，则将数据元素向后移一个位置，当找到插入位置后就将arri-1插入，就完成了arr0,arr1,arrn-1的排序。伪
9、代码如下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是已经排好序的部分数据元素序列，在插入arri时，利用折半查找方法寻找arri的
10、插入位置。折半插入排序方法只能在顺序表存储结构实现。伪代码如下：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趟排序结果为:;for(int t=0;tcurrentsize;t+)co
11、utarrt ;coutendl;num=0; 冒泡排序冒泡排序的基本思想是：设排序表中有n个数据元素。首先对排序表中第一，二个数据元素的关键字arr0和arr1进行比较。如果前者大于后者，则进行交换；然后对第二，三个数据做同样的处理；重复此过程直到处理完最后两个相邻的数据元素。我们称之为一趟冒泡，它将关键字最大的元素移到排序表的最后一个位置，其他数据元素一般也都向排序的最终位置移动。然后进行第二趟排序，对排序表中前n-1个元素进行与上述同样的操作，其结果使整个排序表中关键字次大的数据元素被移到arrn-2的位置。如此最多做n-1趟冒泡就能把所有数据元素排好序。伪代码如下：template /
12、冒泡排序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;简单选择排序（直接选择排序）直接选择排序的算法基
13、本思想是：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; for(int i=0;i=currentsize-1;i+)k=i;for(int j=i+1;jcurrentsize;j+)if(arrjarrk)k=j;/k 指示当前序列中最小者的位置if(k!=i)
14、/最小关键字的数据元素位置不等于iswap(arri,arrk);cout第+num趟排序结果为:;for(int t=0;tcurrentsize;t+)coutarrt ;coutendl;num=0; 快速排序快速排序（Quick Sort）又被称做分区交换排序，这是一种平均性能非常好的排序方法。其算法基本思想是：任取排序表中的某个数据元素(例如取第一个数据元素)作为基准，按照该数据元素的关键字大小，将整个排序表划分为左右两个子表： 左侧子表中所有数据元素的关键字都小于基准数据元素的关键字。右侧子表中所有数据元素的关键字都大于或等于基准数据元素的关键字，基准数据元素则排在这两个子表中间(
15、这也是该数据元素最终应安放的位置)，然后分别对这两个子表重复施行上述方法的快速排序，直到所有的子表长度为1，则排序结束。伪代码如下：template /快速排序void sortlist:quicksort(int low,int high)/在待排序区间low,high上，递归地进行快速排序int i=low,j=high;type temp=arrlow;/取区间第一个位置为基准位置if(ij)while(ij)while(ij&temparrj)j-;if(ij)swap(arri,arrj);i+;while(i=arri)i+;if(ij)swap(arri,arrj);j-;arr
16、i=temp;/将基准元素就位cout第+x趟排序结果为:;for(int t=0;tcurrentsize;t+)coutarrt ;coutendl;quicksort(low,i-1);/在左子区间递归进行快速排序quicksort(i+1,high);/在右子区间递归进行快速排序 堆排序（包括建立最大堆和堆排序两个过程）堆排序算法的基本思想是：a.对排序表中的数据元素，利用堆的调整算法形成初始堆。b.输出堆顶元素。c.对剩余元素重新调整形成堆。d.重复执行第b、c步，直到所有数据元素被输出。 (1)建立最大堆的伪代码如下：template /建立最大堆void sortlist:fil
17、terdown(const int start)/向下调整使从start开始到currentsize-1为止的子表成为最大堆int i=start,j=2*i+1;/j为i的左孩子int tablesize=currentsize;type temp=arri;while(j=currentsize-1)if(jcurrentsize-1 & arrj=arrj)break;elsearri=arrj;i=j;j=2*j+1;arri=temp;(2)堆排序如果建立的堆满足最大堆的条件，则堆的第一个数据元素arr0具有最大的关键字，将arr0与arrn-1对调，把具有最大关键字的数据元素交换到
18、最后，再对前面的n-1个数据元素使用堆的调整算法，重新建立最大堆，结果把具有次最大关键字的数据元素又上浮到堆顶，即arr0的位置，再对调arr0和arrn-2，如此反复执行n-1次，最后得到全部排序好的数据元素序列。伪代码如下：template /堆排序void sortlist:heapsort()int tablesize=currentsize;for(int i=(currentsize-2)/2;i=0;i-)filterdown(i); /初始建堆for(int i=currentsize-1;i=1;i-)swap(arr0,arri);/堆顶元素和最后一个元素交换current
19、size-;filterdown(0);/重建最大堆cout第+num趟排序结果为:;for(int t=0;ttablesize;t+)coutarrt ;coutendl;num=0;currentsize=tablesize; 归并排序（包括归并算法，一趟归并算法和归并排序）归并算法其基本思想是：设有两个有序表A和B，其数据元素个数（表长）分别为n和m，变量i和j分别是表A和表B的当前检测指针；设表C是归并后的新有序表，变量k是它的当前存放指针。开始时i、j、k都分别指向A、B、C三个表的起始位置；然后根据Ai与Bj的关键字的大小，把关键字小的数据元素放到新表Ck中；且相应的检测指针（i
20、或j）和存放指针k增加1.如此循环，当i与j中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表CkCm+n中。下面的归并算法中，两个待归并的有序表首尾相接存放在数组sourcetable.arr中，其中第一个表的下标范围从left到mid，另一个表的下标范围从mid+1到right。前一个表中有mid-left+1个数据元素，后一个表中有right mid个数据元素。归并后得到的新有序表有right mid个数据元素。归并后得到的新有序表存放在另一个辅助数组mergedtable.arr中，其下标范围从left到right。伪代码如下：template void sortlist:mer
21、ge(sortlist&sourcetable,sortlist&mergedtable,const int left,const int mid,const int right)int i=left,j=mid+1,k=left;/指针初始化/i是前一段的当前元素位置，j是后一段的当前元素位置，k是辅助数组的当前位置while(i=mid&j=right)if(sourcetable.arri=sourcetable.arrj)mergedtable.arrk=sourcetable.arri;i+;k+;elsemergedtable.arrk=sourcetable.arrj;j+;k+
22、;if(i=mid)for(int p=k,q=i;q=mid;p+,q+)mergedtable.arrp=sourcetable.arrq;/把前一段复制到mergedtableelsefor(int p=k,q=j;q=right;p+,q+)mergedtable.arrp=sourcetable.arrq;/把后一段复制到mergedtable一趟归并算法设数组sourcetable.arr0到sourcetable.arrn-1中的n个数据元素已经分为一些长度为len的归并项，将这些归并项两两归并，归并成一些长度为2len的归并项，结果放到mergedtable.arr中。如果n不
23、是2len的整数倍，则一趟归并到最后，可能遇到两种情况：剩下一个长度为len的归并项和一个长度不足len的归并项，可用一次merge算法，将它们归并成一个长度小于2len的归并项。只剩下一个归并项，其长度小于或等于len，可将它直接复制到数组mergedtable.arr中。伪代码如下：template template void sortlist:mergepass(sortlist&sourcetable,sortlist&mergedtable,const int len)int i=0;while(i+2*len=currentsize-1)/表示至少有个子序列merge(source
24、table,mergedtable,i,i+len-1,i+2*len-1);i+=2*len;if(i+len=currentsize-1)/若只有最后两个子序列merge(sourcetable,mergedtable,i,i+len-1,currentsize-1);else/若只有最后一个子序列for(int j=i;j=currentsize-1;j+)mergedtable.arrj=sourcetable.arrj;if(len=currentsize-1)if(numcurrentsize) cout第+num趟排序结果为:;for(int t=0;tcurrentsize;t
25、+)coutmergedtable.arrt ;cout=n，因此在则趟归并中while循环不执行，只做把temptable.arr中的数据元素复制到table.arr的工作。伪代码如下：template void sortlist:mergesort(sortlist &table )/按数据元素关键字非递减的顺序对排序表table中数据元素进行递归排序sortlist temptable;int len=1;while(lencurrentsize)mergepass(table,temptable,len);len*=2;mergepass(temptable,table,len);le
26、n*=2; num=0; 主函数主要功能是显示主菜单，以及对各种排序的调用伪代码如下：int main()/主函数 cout *endl;cout 排序问题 endl;cout*endlendlendl;int c=1; char ch;int n1=0;while(c!=0)cout=endl;cout=可供选择的排序方法=endl;cout 1 直接插入排序 2 折半插入排序 endl;cout 3 冒泡排序 4 简单选择排序 endl;cout 5 快速排序 6 堆排序 endl;cout 7 归并排序 0 退出排序程序 endl; cout =endl;coutch;if(ch=0)
27、cout 您已成功退出该系统!=0&ch=7)coutn;coutn 请输入n个数：;sortlisttable(n);for(int i=0;inumber;table.insert(i,number);switch(ch) case 1:coutn *您选择的是直接插入排序*nendl;table.insertionsort();break;system(pause);break;case 2:coutn *您选择的是折半插入排序*nendl;table.binaryinsertsort();break;system(pause);break;case 3:coutn *您选择的是冒泡排序
28、*nendl;table.bubblesort();break;system(pause);break;case 4:coutn *您选择的是简单选择排序*nendl;table.selectsort();break;system(pause);break;case 5:coutn *您选择的是快速排序*nendl;table.quicksort(0,n-1);break;system(pause);break;case 6:coutn *您选择的是堆排序*nendl;table.heapsort();break;system(pause);break;case 7:coutn *您选择的是归
29、并排序*nendl;table.mergesort(table);break;system(pause);break; system(pause);return 0;三 上机结果及体会1) 实际完成的情况说明此程序主要实现了对不同排序算法的演示，并给出了每一趟的变化情况2) 程序的性能分析a. 直接插入排序（稳定的排序方法）1时间复杂度a) 若待排序记录按关键字从小到大排列(正序)关键字比较次数：记录移动次数：2(n-1)b)若待排序记录按关键字从大到小排列(逆序)关键字比较次数：记录移动次数： c) 若待排序记录是随机的，取最好和最坏情况的平均值关键字比较次数(约为)：记录移动次数(约为)：
30、 2空间复杂度：S(n)=O(1)b. 折半插入排序（稳定的排序算法）就平均性能而言，因为折半查找优于顺序查找，所以折半插入排序也优于直接插入排序。关键字的比较次数为：n*log2(n)c. 冒泡排序（稳定的排序算法）1. 时间复杂度：a) 最好情况（正序）b) 比较次数：n-1（只要进行一趟即可）c) 移动次数：0d) 最坏情况（逆序）e) 比较次数：（需n-1趟，每趟达到最大比较次数） f) 移动次数：在最坏情况下，时间复杂度为:T(n)=O(n)2. 空间复杂度：S(n)=O(1)d. 简单选择排序（不稳定的排序方法）1. 时间复杂度：O(n2)。2. 空间复杂度：S(1)。 e. 快速
31、排序（不稳定的排序方法）1.时间复杂度最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n)最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n) 2.空间复杂度：需栈空间以实现递归最坏情况：S(n)=O(n)一般情况：S(n)=O(log2n) f. 堆排序（不稳定的排序方法） 1.间复杂性为O(nlog2n)。 2空间复杂性为O(1)。g. 归并排序（稳定的排序方法） 1时间复杂度为O(nlog2n)。 2空间复杂度为O(n）。 3）运行情况主菜单直接插入排序折半插入排序冒泡排序简单选择排序快速排序堆排序归并排序退出系统3) 上机过程中出现的问题及其解决方案1 快速排序时
32、出现多一次排序的情况 解决方法：在进行循环体时，多运行了一次，将运行次序减1即可。2 堆排序时也出现与上一条相同的情况 解决方法：由于缺少一个判断语句导致输出只能是偶数倍趟数，因此加一条if(len=currentsize-1)判断语句就可以使程序正常输出结果3 快速排序趟数开始为1 ,2 ,1, 2出现 解决方法：再定义一个全局变量，不过当其用完时，没有将它重新置为0，这样最后输出的趟数就正确了。4 运行程序时，若输入字符，则必须输入完全后，才判断其为不正确的选择 解决方法：加一个if判断语句即可4) 程序中可以改进的地方说明本程序不能判断字符数大于1的字符串，这方面需要改进可以在程序中加入
33、性能分析，例如空间复杂度，时间复杂度等5) 程序中可以扩充的功能及其设计实现假想扩充功能：可以加入希尔排序等未加入的排序方法，可以加入性能分析实现假想：加入其他排序方法后，输出为正确排序的过程，加入性能分析时，输出排序过程的同时，可以输出时间复杂度与空间复杂度6) 收获及体会在进行为期一个星期的课程设计中，最终完成了算法。这期间，遇到的各种麻烦也都相继解决。从这次实践中，我意识到自己还有很多不足之处。首先先说一下基本的。对于各种排序算法的过程还是不够熟悉，进行编程时还需要翻书查找，对于这一点，只能说对数据结构的学习还不够扎实，虽然说这门课程以后就没有了，但是我想这门课对以后的学习会有很大帮助，
34、所以有空时还应该继续熟悉这门课程。其次，就是对于错误的处理，不能得心应手，不能正确处理一些简单的错误。对于逻辑上的错误，不能够立即找到出错点，往往需要向同学请教才能找出错误，并且改正。我觉得这是自己独自思考能力不高的问题，遇事需要自己仔细想想，若还不能改正，再请教别人也不迟。从总体上说，整个代码的实现还是存在不足的，例如本程序不能判断字符数大于1的字符串，没有相应排序的性能分析（如空间复杂度，时间复杂度），等等。从这点看，说明自己的程序还是不够完善，不能做到十全十美，希望以后能有所修正。总而言之，从这次的实践中我学到了很多东西，希望以后能够多加运应 7) 源代码：#include stdafx
35、.h#includeusing namespace std;const int maxsize=100;int num=0;/定义全局变量，为每一趟的输出做准备int x=0;templateclass sortlistprivate:int currentsize;/数据表中数据元素的个数public:type *arr;/存储数据元素的向量（排序表）sortlist():currentsize(0)arr=new typemaxsize;/构造函数sortlist(int n)arr=new typemaxsize;currentsize=n;void insert(int i,type x)arri=x;sortlist()delete arr;/析构函数v