西北工业大学-程序设计大作业

学院××××学院班级××××××××学号××××××××姓名×××Email:[e-mail]2目录1摘要.................................................................................................31.1设计题目..................................................................................31.2设计内容..................................................................................31.3开发工具..................................................................................31.4应用平台..................................................................................32详细设计.........................................................................................32.1程序结构..................................................................................32.2主要功能..................................................................................42.3函数实现..................................................................................52.4开发日志..................................................................................73程序调试及运行.............................................................................73.1程序运行结果...........................................................................73.2程序使用说明.........................................................................123.3程序开发总结.........................................................................124附件（源程序）...........................................................................12Email:[e-mail]31摘要1.1设计题目算法型大作业题目：编写七种排序算法的演示程序。1.2设计内容编写快速排序、插入排序、选择排序、冒泡排序、堆排序、归并排序、基数排序函数，通过主函数调用以实现七种排序算法的演示。1.3开发工具VisualC++6.01.4应用平台Windows2000/XP/Vista32位2详细设计2.1程序结构程序的整体结构与流程见下图所示。程序运行时在主菜单中输入序号选择排序方法或选择结束程序，当进行某种排序方法后，在主函数中输入待排数据个数和待排数据，通过调用对应的排序函数实现排序并输出。该排序结束后再次进入主函数，通过循环重复上述操作。其中，主函数中将数组地址和待排序数据个数传递给排序函数，在排序函数中实现排序功能。Email:[e-mail]42.2主要功能函数的功能为对快速排序、插入排序、选择排序、冒泡排序、堆排序、归并排序、基数排序算法的演示。主函数：程序运行时，可使运行者根据提醒输入相关操作，从而进入不同的排序方法或者退出。快速排序函数：根据快速排序的算法，最后输出插入排序函数：根据插入排序的算法，最后输出选择排序函数：根据选择排序的算法，最后输出冒泡排序函数：根据冒泡排序的算法，最后输出堆排序函数：根据堆排序的算法，最后输出归并排序函数：根据归并排序的算法，最后输出基数排序函数：根据基数排序的算法，最后输出开始进入主菜单选择排序方法输出排序结果快速插入选择冒泡堆排归并基数退出系统Email:[e-mail]52.3函数实现主函数:在主函数中对菜单输出，通过switch语句中的case分支选择所需要的排序方法；通过while循环使演示程序在运行时能够持续进行快速排序：快速排序（kuaisu）又被称做分区交换排序，这是一种平均性能非常好的排序方法。其算法基本思想是：任取排序表中的某个数据元素(例如取第一个数据元素)作为基准，按照该数据元素的关键字大小，将整个排序表划分为左右两个子表：左侧子表中所有数据元素的关键字都小于基准数据元素的关键字。右侧子表中所有数据元素的关键字都大于或等于基准数据元素的关键字，基准数据元素则排在这两个子表中间(这也是该数据元素最终应安放的位置)，然后分别对这两个子表重复施行上述方法的快速排序，直到所有的子表长度为1，则排序结束。插入排序：插入排序（charu）的基本思想：开始时把第一个数据元素作为初始的有序序列，然后从第二个数据元素开始依次把数据元素按关键字大小插入到已排序的部分排序表的适当位置。当插入第i(1i=n)个数据元素时，前面的i-1个数据元素已经排好序，这时，用第i个数据元素的关键字与前面的i-1个数据元素的关键字顺序进行比较，找到插入位置后就将第i个数据元素插入。如此进行n-1次插入，就完成了排序。以下是在顺序表上实现的直接插入排序在顺序表上进行直接插入排序时，当插入第i(1i=n)个数据元素时，前面的A[0]、A[1]、…、A[i-2]已经排好序，这时，用A[i-1]的关键字依次与A[i-2],A[i-3],…的关键字顺序进行比较，如果这些数据元素的关键字大于A[i-1]的关键字，则将数据元素向后移一个位置，当找到插入位置后就将A[i-1]插入，就完成了A[0],A[1],…,A[n-1]的排序。选择排序选择排序（xuanze）的算法基本思想是：a)开始时设i的初始值为0。b)如果in-1，在数据元素序列A[i](A[n-1]中，选出具有最小关键字的数据元素A[k]；否则算法结束。c)若A[k]不是这组数据元素中的第一个数据元素（i≠k），则将A[k]与A[i]这两数据元素的位置对调；d)令i=i+1转步骤b)。冒泡排序：冒泡排序(maopao)的基本思想是：设排序表中有n个数据元素。首先对排序表中第一，二个数据元素的关键字A[0]和A[1]进行比较。如果前者大于后者，则进行交换；然后对第二，三个数据做同样的处理；重复此过程直到处理完最后两个相邻的数据元素。我们称之为一趟冒泡，它将关键字最大的元素移到排序表的最后一个位置，其他数据元素一般也都向排序的最终位置移动。然后进行第二趟排序，对排序表中前n-1个元素进行与上述同样的操作，其结果使整个排序表中关键字次大的数据元素被移到A[n-2]的位置。如此最多做n-1趟冒泡就能把所有数据元素排好序。Email:[e-mail]6堆排序：堆排序(duipai)sa.对排序表中的数据元素，利用堆的调整算法形成初始堆。b.输出堆顶元素。c.对剩余元素重新调整形成堆。d.重复执行第b、c步，直到所有数据元素被输出。如果建立的堆满足最大堆的条件，则堆的第一个数据元素A[0]具有最大的关键字，将A[0]与A[n-1]对调，把具有最大关键字的数据元素交换到最后，再对前面的n-1个数据元素使用堆的调整算法，重新建立最大堆，结果把具有次最大关键字的数据元素又上浮到堆顶，即A[0]的位置，再对调A[0]和A[n-2]，…，如此反复执行n-1次，最后得到全部排序好的数据元素序列。归并排序：其基本思想是：设有两个有序表A和B，其数据元素个数（表长）分别为n和m，变量i和j分别是表A和表B的当前检测指针；设表C是归并后的新有序表，变量k是它的当前存放指针。开始时i、j、k都分别指向A、B、C三个表的起始位置；然后根据A[i]与B[j]的关键字的大小，把关键字小的数据元素放到新表C[k]中；且相应的检测指针（i或j）和存放指针k增加1.如此循环，当i与j中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表C[k]~C[m+n]中。下面的归并算法中，两个待归并的有序表首尾相接存放在数组sourcetable.arr[]中，其中第一个表的下标范围从left到mid，另一个表的下标范围从mid+1到right。前一个表中有mid-left+1个数据元素，后一个表中有right–mid个数据元素。归并后得到的新有序表有right–mid个数据元素。归并后得到的新有序表存放在另一个辅助数组mergedtable.arr[]中，其下标范围从left到right。一趟归并算法：设数组sourcetable.arr[0]到sourcetable.arr[n-1]中的n个数据元素已经分为一些长度为len的归并项，将这些归并项两两归并，归并成一些长度为2len的归并项，结果放到mergedtable.arr[]中。如果n不是2len的整数倍，则一趟归并到最后，可能遇到两种情况：剩下一个长度为len的归并项和一个长度不足len的归并项，可用一次merge算法，将它们归并成一个长度小于2len的归并项。只剩下一个归并项，其长度小于或等于len，可将它直接复制到数组mergedtable.arr[]中。在一趟归并算法的基础上，实现两路归并排序算法。在两路归并排序算法中，初始排序表存放在数组table.arr[]中,第一趟归并将table.arr[]中的归并项两两归并，结果存放在辅助数组temptable.arr[]中。第二趟将temptable.arr[]中的归并项两两归并，结果放回原数组table.arr[]中，如此反复进行。为了将最后归并结果仍放在数组table.arr[]中，归并趟数应为偶数。如果做奇数趟就能完成时，最后还需要执行一次一趟归并过程，由于这时的归并项长度len=n，因此在则趟归并中while循环不执行，只做把temptable.arr[]中的数据元素复制到table.arr[]的工作。基数排序：“基数排序法”（radixsort）则是属于“分配式排序”（distributionsort），基数排序法又称“桶子法”（bucketsort）或binsort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。具体可以参看后面的代码进行理解。Email:[e-mail]7其它：使用了stdlib头文件里包含的系统函数，包括清屏函数和运行时的暂停，增强了程序运行时的效果。2.4开发日志在老师布置了大作业的题目后，我就把题目下载下来并进行分析已选择合适的题目。经过我的慎重考虑，选择了算法型大作业题目中的编写七种排序算法的演示程序，觉得自己有能力把这道题目很好完成。在认真分