数据结构课程设计报告---几种排序算法的演示(附源代码)

.............数据结构课程设计报告—几种排序算法的演示时间：2010-1-14一需求分析运行环境.............MicrosoftVisualStudio2005程序所实现的功能对直接插入排序、折半插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序算法的演示，并且输出每一趟的排序情况。程序的输入（包含输入的数据格式和说明）1排序种类三输入2排序数的个数的输入3所需排序的所有数的输入程序的输出（程序输出的形式）1主菜单的输出2每一趟排序的输出，即排序过程的输出二设计说明算法设计思想1交换排序（冒泡排序、快速排序）交换排序的基本思想是：对排序表中的数据元素按关键字进行两两比较，如果发生逆序（即排列顺序与排序后的次序正好相反），则两者交换位置，直到所有数据元素都排好序为止。2插入排序（直接插入排序、折半插入排序）插入排序的基本思想是：每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列，它只包含一个数据元素。然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序列后，整个排序工作就完成了。3选择排序（简单选择排序、堆排序）选择排序的基本思想是：第一趟在有n个数据元素的排序表中选出关键字最小的数据元素，然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素，依次重复，每一趟（例如第i趟，i=1，…，n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。等到第n-1趟选择结束，待排序数据元素仅剩下一个时就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。4归并排序（两路归并排序）两路归并排序的基本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为1的首尾相接的n个有序子表（以后称它们为归并项），先做两两归并，得n/2上取整个长度为2的归并项（如果n为奇数，则最后一个归并项的长度为1）；再做两两归并，……，如此重复，最后得到一个长度为n的有序序列。.............程序的主要流程图程序的主要模块(要求对主要流程图中出现的模块进行说明)程序的主要模块主要分为主菜单模块和排序算法演示模块。1主菜单主要功能：程序运行时，可使运行者根据提醒输入相关操作，从而进入不同的排序方法或者退出。2排序方法及输出根据运行者对排序的不同选择，进入排序过程开始进入主菜单选择排序方法输出排序结果直插折半冒泡选择快排堆排归并退出系统.............a.直接插入排序：根据直接排序的算法，输出排序过程b.折半插入排序：根据折半插入的算法，输出排序过程c.冒泡排序：根据冒泡排序算法，输出排序过程d.简单选择排序：根据简单选择排序的算法，输出排序过程e.快速排序：根据快速排序的算法，输出排序过程f.堆排序：根据堆排序的算法，输出排序过程g.归并排序：根据归并排序的算法，输出排序过程程序的主要函数及其伪代码说明1模板类主要说明程序中用到的类的定义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;}voidbubblesort();//冒泡排序voidquicksort(intlow,inthigh);//快速排序voidinsertionsort();//直接插入排序voidbinaryinsertsort();//折半插入排序voidselectsort();//简单选择排序voidheapsort();//堆排序voidmergesort(sortlisttype&table);//归并排序voidfilterdown(constintstart);//建立最大堆voidmergepass(sortlisttype&sourcetable,sortlisttype&mergedtable,constintlen);//一趟归并voidmerge(sortlisttype&sourcetable,sortlisttype&mergedtable,constintleft,constintmid,constintright);//两路归并算法};2直接插入排序直接插入排序的基本思想：开始时把第一个数据元素作为初始的有序序列，然后从第二个数据元素开始依次把数据元素按关键字大小插入到已排序的部分排序表的适当位置。当插入第i(1i=n)个数据元素时，前面的i-1个数据元素已经排好序，这时，用第i个数据元素的关键字与前面的i-1个数据元素的关键字顺序进行比较，找到插入位置后就将第i个数据元素插入。如此进行n-1次插入，就完成了排序。以下是在顺序表上实现的直接插入排序.............在顺序表上进行直接插入排序时，当插入第i(1i=n)个数据元素时，前面的arr[0]、arr[1]、…、arr[i-2]已经排好序，这时，用arr[i-1]的关键字依次与arr[i-2],arr[i-3],…的关键字顺序进行比较，如果这些数据元素的关键字大于arr[i-1]的关键字，则将数据元素向后移一个位置，当找到插入位置后就将arr[i-1]插入，就完成了arr[0],arr[1],…,arr[n-1]的排序。伪代码如下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;}3折半插入排序折半插入排序的基本思想：设在排序表中有n个数据元素arr[0],arr[1],…,arr[n-1]。其中，arr[0],arr[1],…,arr[n-1]是已经排好序的部分数据元素序列，在插入arr[i]时，利用折半查找方法寻找arr[i]的插入位置。折半插入排序方法只能在顺序表存储结构实现。伪代码如下：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;}4冒泡排序冒泡排序的基本思想是：设排序表中有n个数据元素。首先对排序表中第一，二个数据元素的关键字arr[0]和arr[1]进行比较。如果前者大于后者，则进行交换；然后对第二，三个数据做同样的处理；重复此过程直到处理完最后两个相邻的数据元素。我们称之为一趟冒泡，它将关键字最大的元素移到排序表的最后一个位置，其他数据元素一般也都向排序的最终位置移动。然后进行第二趟排序，对排序表中前n-1个元素进行与上述同样的操作，其结果使整个排序表中关键字次大的数据元素被移到arr[n-2]的位置。如此最多做n-1趟冒泡就能把所有数据元素排好序。伪代码如下：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;}5简单选择排序（直接选择排序）.............直接选择排序的算法基本思想是：a)开始时设i的初始值为0。b)如果in-1，在数据元素序列arr[i]arr[n-1]中，选出具有最小关键字的数据元素arr[k]；否则算法结束。c)若arr[k]不是这组数据元素中的第一个数据元素（i≠k），则将arr[k]与arr[i]这两数据元素的位置对调；d)令i=i+1转步骤b)。伪代码如下：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;}6快速排序快速排序（QuickSort）又被称做分区交换排序，这是一种平均性能非常好的排序方法。其算法基本思想是：任取排序表中的某个数据元素(例如取第一个数据元素)作为基准，按照该数据元素的关键字大小，将整个排序表划分为左右两个子表：左侧子表中所有数据元素的关键字都小于基准数据元素的关键字。右侧子表中所有数据元素的关键字都大于或等于基准数据元素的关键字，基准数据元素则排在这两个子表中间(这也是该数据元素最终应安放的位置)，然后分别对这两个子表重复施行上述方法的快速排序，直到所有的子表长度为1，则排序结束。伪代码如下：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(a