搜索
数据结构课程设计报告几种排序算法的演示一、需求分析：1、运行环境：MicrosoftVisualStudio20052、程序实现功能：通过用户键入的数据，经过程序进行排序，最后给予数据由小到大的输出。排序的方式包含教材中所介绍的几种常用的排序方式：直接插入排序、折半插入排序、冒泡排序、快速排序、选择排序、堆排序、归并排序。每种排序过程中均显示每一趟排序的细节。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模板类templateclasstypeclasssortlist{private:intcurrentsize;//数据表中数据元素的个数public:type*arr;//存储数据元素的向量（排序表）开始主菜单选择排序操作直接插入折半插入冒泡排序快速排序简单选择堆排序归并排序退出排序系统输出各趟排序结果sortlist():currentsize(0){arr=newtype[maxsize];}//构造函数sortlist(intn){arr=newtype[maxsize];currentsize=n;}voidinsert(inti,typex){arr[i]=x;}~sortlist(){delete[]arr;}//析构函数voidswap(type&x,type&y)//数据元素x和y交换位置{typetemp=x;x=y;y=temp;}voidinsertionsort();//直接插入排序voidbinaryinsertsort();//折半插入排序voidbubblesort();//冒泡排序voidselectsort();//简单选择排序voidquicksort(intlow,inthigh);//快速排序voidheapsort();//堆排序voidmergesort(sortlisttype&table);//归并排序voidfilterdown(constintstart);//建立最大堆voidmergepass(sortlisttype&sourcetable,sortlisttype&mergedtable,constintlen);//一趟归并voidmerge(sortlisttype&sourcetable,sortlisttype&mergedtable,constintleft,constintmid,constintright);//两路归并算法}b直接插入排序templateclasstype//直接插入排序voidsortlisttype::insertionsort(){templateclasstype//直接插入排序voidsortlisttype::insertionsort(){typetemp;intj;for(inti=1;i=currentsize-1;i++){temp=arr[i];j=i-1;while(j=0&&temparr[j]){arr[j+1]=arr[j];j--;}arr[j+1]=temp;cout第++num趟排序结果为:;for(intt=0;tcurrentsize;t++)coutarr[t];coutendl;}num=0;}c折半插入排序：templateclasstype//折半插入排序voidsortlisttype::binaryinsertsort(){typetemp;intleft,right;for(inti=1;icurrentsize;i++){left=0;right=i-1;temp=arr[i];while(left=right)//找插入位置{intmid=(left+right)/2;if(temparr[mid])right=mid-1;elseleft=mid+1;}for(intk=i-1;k=left;k--)//向后移动arr[k+1]=arr[k];arr[left]=temp;cout第++num趟排序结果为:;for(intt=0;tcurrentsize;t++)coutarr[t];coutendl;}num=0;}d冒泡排序templateclasstype//冒泡排序voidsortlisttype::bubblesort(){inti=1;intfinish=0;//0表示还没有排好序while(icurrentsize&&!finish){finish=1;//排序结束标志置为,假定已经排好序for(intj=0;jcurrentsize-i;j++)if(arr[j]arr[j+1])//逆序{swap(arr[j],arr[j+1]);//相邻元素交换位置finish=0;}//排序结束标志置为,表示本趟发生了交换，说明还没有排好序i++;cout第++num趟排序结果为:;for(intt=0;tcurrentsize;t++)coutarr[t];coutendl;}num=0;}e简单选择排序templateclasstypevoidsortlisttype::selectsort()//简单选择排序{intk;for(inti=0;i=currentsize-1;i++){k=i;for(intj=i+1;jcurrentsize;j++)if(arr[j]arr[k])k=j;//k指示当前序列中最小者的位置if(k!=i)//最小关键字的数据元素位置不等于iswap(arr[i],arr[k]);cout第++num趟排序结果为:;for(intt=0;tcurrentsize;t++)coutarr[t];coutendl;}num=0;}f快速排序：templateclasstype//快速排序voidsortlisttype::quicksort(intlow,inthigh)//在待排序区间[low,high]上，递归地进行快速排序{inti=low,j=high;typetemp=arr[low];//取区间第一个位置为基准位置if(ij){while(ij){while(ij&&temparr[j])j--;if(ij){swap(arr[i],arr[j]);i++;}while(ij&&temp=arr[i])i++;if(ij){swap(arr[i],arr[j]);j--;}}arr[i]=temp;//将基准元素就位cout第++x趟排序结果为:;for(intt=0;tcurrentsize;t++)coutarr[t];coutendl;quicksort(low,i-1);//在左子区间递归进行快速排序quicksort(i+1,high);//在右子区间递归进行快速排序}}g堆排序(1)建立最大堆的伪代码如下：templateclasstype//建立最大堆voidsortlisttype::filterdown(constintstart){//向下调整使从start开始到currentsize-1为止的子表成为最大堆inti=start,j=2*i+1;//j为i的左孩子inttablesize=currentsize;typetemp=arr[i];while(j=currentsize-1){if(jcurrentsize-1&&arr[j]arr[j+1])j++;//在两个孩子中选关键字较大者if(temp=arr[j])break;else{arr[i]=arr[j];i=j;j=2*j+1;}}arr[i]=temp;}(2)堆排序templateclasstype//堆排序voidsortlisttype::heapsort(){inttablesize=currentsize;for(inti=(currentsize-2)/2;i=0;i--)filterdown(i);//初始建堆for(inti=currentsize-1;i=1;i--){swap(arr[0],arr[i]);//堆顶元素和最后一个元素交换currentsize--;filterdown(0);//重建最大堆cout第++num趟排序结果为:;for(intt=0;ttablesize;t++)coutarr[t];coutendl;}num=0;currentsize=tablesize;}h归并排序归并算法：templateclasstypevoidsortlisttype::merge(sortlisttype&sourcetable,sortlisttype&mergedtable,constintleft,constintmid,constintright){inti=left,j=mid+1,k=left;//指针初始化//i是前一段的当前元素位置，j是后一段的当前元素位置，k是辅助数组的当前位置while(i=mid&&j=right)if(sourcetable.arr[i]=sourcetable.arr[j]){mergedtable.arr[k]=sourcetable.arr[i];i++;k++;}else{mergedtable.arr[k]=sourcetable.arr[j];j++;k++;}if(i=mid)for(intp=k,q=i;q=mid;p++,q++)mergedtable.arr[p]=sourcetable.arr[q];//把前一段复制到mergedtableelsefor(intp=k,q=j;q=right;p++,q++)mergedtable.arr[p]=sourcetable.arr[q];//把后一段复制到merge