数据结构课程设报告—各种排序算法的比较.docx

数据结构课程设计报告几种排序算法的演示一、 需求分析：1、 运行环境：Microsoft Visual Studio 2005 2、 程序实现功能：通过用户键入的数据，经过程序进行排序，最后给予数据由小到大的输出。排序的方式包含教材中所介绍的几种常用的排序方式：直接插入排序、折半插入排序、冒泡排序、快速排序、选择排序、堆排序、归并排序。每种排序过程中均显示每一趟排序的细节。3、 程序的输入：输入所需排序方式的序号。输入排序的数据的个数。输入具体的数据元素。4、 程序的输出：输出排序每一趟的结果，及最后排序结果二、 设计说明：1、 算法设计思想：a交换排序（冒泡排序、快速排序）交换排序的基本思想是：对排序表中的数据元素按关键字进行两两比较，如果发生逆序（即排列顺序与排序后的次序正好相反），则两者交换位置，直到所有数据元素都排好序为止。 b插入排序（直接插入排序、折半插入排序）插入排序的基本思想是：每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列，它只包含一个数据元素。然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序列后，整个排序工作就完成了。 c选择排序（简单选择排序、堆排序）选择排序的基本思想是：第一趟在有n个数据元素的排序表中选出关键字最小的数据元素，然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素，依次重复，每一趟（例如第i趟，i=1，n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。等到第n-1趟选择结束，待排序数据元素仅剩下一个时就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。 d归并排序（两路归并排序）两路归并排序的基本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为1的首尾相接的n个有序子表（以后称它们为归并项），先做两两归并，得n/2上取整个长度为2的归并项（如果n为奇数，则最后一个归并项的长度为1）；再做两两归并，如此重复，最后得到一个长度为n的有序序列。1、 主要的数据结构设计说明：程序的数据结构为：堆、线性表；2、 程序的主要流程图：开始主菜单选择排序操作归并排序堆排序简单选择快速排序冒泡排序折半插入直接插入输出各趟排序结果退出排序系统3、 程序的主要模块，A 主菜单B 排序模块： a 直接插入排序 b 折半插入排序 c 冒泡排序 d 快速排序 e 简单选择排序 f 堆排序 g 归并排序4、程序的主要函数及其伪代码a模板类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;/析构函数 void swap(type &x,type &y)/数据元素x和y交换位置 type temp=x;x=y;y=temp;void insertionsort();/直接插入排序void binaryinsertsort();/折半插入排序void bubblesort();/冒泡排序void selectsort();/简单选择排序void quicksort(int low,int high);/快速排序 void heapsort();/堆排序 void mergesort(sortlist &table);/归并排序 void filterdown(const 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);/两路归并算法 b 直接插入排序 template /直接插入排序void sortlist:insertionsort()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; c 折半插入排序： 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+)coutarrt ;coutendl;num=0;d冒泡排序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; e 简单选择排序 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)/最小关键字的数据元素位置不等于iswap(arri,arrk);cout第+num趟排序结果为:;for(int t=0;tcurrentsize;t+)coutarrt ;coutendl;num=0; f 快速排序：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-;arri=temp;/将基准元素就位cout第+x趟排序结果为:;for(int t=0;tcurrentsize;t+)coutarrt ;coutendl;quicksort(low,i-1);/在左子区间递归进行快速排序quicksort(i+1,high);/在右子区间递归进行快速排序 g 堆排序 (1)建立最大堆的伪代码如下：template /建立最大堆void sortlist:filterdown(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)堆排序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);/堆顶元素和最后一个元素交换currentsize-;filterdown(0);/重建最大堆cout第+num趟排序结果为:;for(int t=0;ttablesize;t+)coutarrt ;coutendl;num=0;currentsize=tablesize;h 归并排序归并算法：template void sortlist:merge(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+;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一趟归并算法template template void sortlist:mergepass(sortlist&sourcetable,sortlist&mergedtable,const int len)int i=0;while(i+2*len=currentsize-1)/表示至少有个子序列merge(sourcetable,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+)coutmergedtable.arrt ;coutendl; 归并排序：template void sortlist:mergesort(sortlist &table )/按数据元素关键字非递减的顺序对排序表table中数据元素进行递归排序sortlist temptable;int len=1;while(lencurrentsize)mergepass(table,temptable,len);len*=2;mergepass(temptable,table,len);len*=2; num=0; i 主函数int main()/主函数 int c=1; char ch,cc;int n1=0;while(c!=0)cout请选择排序的方法endl;cout 1 直接插入排序 2 折半插入排序 endl;cout 3 冒泡排序 4 简单选择排序 endl;cout 5 快速排序 6 堆排序 endl;cout 7 归并排序 0 退出排序程序 endl; coutendl;coutch;if(ch=0) 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您选择的是冒泡排序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您选择的是归并排序nendl;table.mergesort(table);break;system(pause);break; system(pause);return 0;三、 上机结果及体会：a. 程序的性能分析，时空分析：直接插入排序（稳定的排序方法）1时间复杂度a)若待排序记录按关键字从小到大排列(正序)关键字比较次数：记录移动次数：2(n-1)b)若待排序记录按关键字从大到小排列(逆序)关键字比较次数：记录移动次数： c) 若待排序记录是随机的，取最好和最坏情况的平均值 关键字比较次数(约为)：记录移动次数(约为)：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. 快速排序（不稳定的排序方法）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）。 1、 程序运行时的初值和运行结果，主菜单：直接插入排序：折半插入排序：冒泡排序：简单选择排序：快速排序：堆排序：归并排序：退出排序：2、 收获和体会：在进行为期一个星期的课程设计中，最终完成了算法。这期间，遇到的各种麻烦也都相继解决。从这次实践中，我意识到自己还有很多不足之处。首先先说一下基本的。对于各种排序算法的过程还是不够熟悉，进行编程时还需要翻书查找，对于这一点，只能说对数据结构的学习还不够扎实，还需要在以后的学习中多多注意C+语言的学习和数据结构的相关知识。其次，就是对于错误的处理，不能得心应手，不能正确处理一些简单的错误。对于逻辑上的错误，不能够立即找到出错点，往往需要向同学请教才能找出错误，并且改正。从总体上说，整个代码的实现还是存在不足的，例如本程序不能判断字符数大于1的字符串，没有相应排序的性能分析（如空间复杂度，时间复杂度），等等。从这点看，说明自己的程序还是不够完善，不能做到十全十美，希望以后能有所修正。总而言之，从这次的实践中我学到了很多东西，在以后的学习生活中要多多注意整顿自己的学风，严谨踏实的面对学习之中的问题。3、 源程序代码：#include stdafx.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;/析构函数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(const 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);/两路归并算法;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;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+)coutarrt ;coutendl;num=0;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;template void sortlist:selectsort()/简单选择排序int k; for(int i=0;icurrentsize-1;i+)k=i;for(int j=i+1;jcurrentsize;j+)if(arrjarrk)k=j;/k 指示当前序列中最小者的位置if(k!=i)/最小关键字的数据元素位置不等于iswap(arri,arrk);cout第+num趟排序结果为:;for(int t=0;tcurrentsize;t+)coutarrt ;coutendl;num=0;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-;arri=temp;/将基准元素就位cout第+x趟排序结果为:;for(int t=0;tcurrentsize;t+)coutarrt ;coutendl;quicksort(low,i-1);/在左子区间递归进行快速排序quicksort(i+1,high);/在右子区间递归进行快速排序template /建立最大堆void sortlist:filterdown(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;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);/堆顶元素和最后一个元素交换currentsize-;filterdown(0);/重建最大堆cout第+num趟排序结果为:;for(int t=0;ttablesize;t+)coutarrt ;coutendl;num=0;currentsize=tablesize;template void sortlist:merge(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+;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;/把后一段复制到mergedtabletemplate void sortlist:mergepass(sortlist&sourcetable,sortlist&mergedtable,const int len)int i=0;while(i+2*len=currentsize-1)/表示至少有个子序列merge(sourcetable,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=cu