文档介绍：:..—、需求分析概要说明本组设计的各种排序算法,用菜单实现选择某种排序算法。用程序实现直接插入排序算法、折半插入排序算法、谢尔排序算法、选择排序算法、堆排序算法、2-路归并排序算法、冒泡排序算法。输入的数据形式为任何一个正整数(大小不限),输出数字大小逐个递增的数列。程序的控制设计,不论是多简单的程序,都应该有良好的用户界而,只要程序一运行,就能从显示内容上看出这个是干什么的程序,能根据提示进行输入输出。可以设置多级菜单,用于各级功能模块的入口,并控制好如何返冋,虽然实现的功能跟顺序执行的一样,但增加了不少灵活性,一个程序就应该尽最大努力来适应用户而不是让用户来适应程序。在具体函数的实现上也要好好斟酌算法,用以节省CPU和内存资源。在系统软件和应用软件的开发设计过程屮,都会不可能避免地遇到这样排序问题。在数据库和知识库管理系统中,排序应用更为广泛。在现今的高级计算机体系结构中,花费在排序上的时间占系统cpu时间的比重很大,据统计,在一些商用计算机系统中,花费在排序操作上的时间占cpu的时间可高达15%-75%。可见,排序是值得深入研究和认真剖析的有趣课题。二概要设计1•简要说明本组设计的功能利用不同的算法尽量缩短时间复杂度,提高查找时间效率,能够将一个案值无序的数据元素序列转换成一个案值有序的数据元素序列。木设计由7个被调用函数和一个主函数组成。先通过主函数miari()登录界面,显示菜单(不同的排序方法),申请一个动态空间(*c)即数组长度(排序的个数),然后输入数字排序的个数;再输入相应排序个数的数字即任何一个正整数(大小不限)。然后输入排序算法的序号,是通过switch函数选择排序的算法(调用算法函数),由用户自己选择。最后通过for循环语句将按数字大小逐个递增的数列输出。程序的主要子函数声明如下:冒泡排序算法:折半排序算法:谢尔排序算法:插入排序算法:选择排序算法:堆积排序算法:voidBubbleSort(int*k,intCount);voidbin_insertsort(int*k,intn);voidshe11sort(int*k,intn);voidinsertsort(int*k,intn);voidselectsort(int*k,intn);voidadjust(int*k,inti,intn);二路归并排序算法:voidMergeSort(RecTypeR[],intIow,inthigh)【通过voidMerge(RecType*R,intlow,intm,inthigh)]实现这种算法;通过这些不同的算法实现数字大小的排序。本程序利用一维数组,先定义一个动态数组:c二(int*)caIIoc(n,sizeof(int));通过sancf语句将输入n值;n表示输入多少个排序的数字。利用for(i=1;i<=n;i++)和scanfC'%d",&c[i])将排序的数字输入。然后通过菜单选者你想用的排序算法进行排序(数组),再通过for循坏语句将排好序数字依次输出。冒泡排序基本思想:将n个记录看作按纵向排列,每趟排序时自下至上对每对相邻记录进行比较,若次序不符合要求(逆序)就交换。每趟排序结束吋都能使排序范围内关键字最小的记录象一个气泡一样升到表上端的对应位置,整个排序过程共进行n・l趟,依次将关键字最小、次小、第三小…的各个记录“冒到”表的第一个、第二个、第三个…位置上。希尔排序基本思想:先取一个小于n的整数c[1]作为第一个增量,把文件的全部记录分成d1个组。所有距离为c[1]的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量c[2]<c[1]重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<...<d2<d1),即所有记录放在同一组中进行直接插入排序为止。插入排序基本思想:先当前被插入元素k[i]保存在temp中,第i趟排序将序列中的第i+1个元素ki+1(i=l,2……,n-l)插入到一个已经排好序的子序列(kl,k2,k3,……,ki)的合适位置,得到一个长度为i+1且仍然保持按值有序的子序列(kl,k2,k3, ,ki,ki+1)。插入排序方法的核心动作是插入,而寻找被插入元素的合适位置是主要的工作。折半排序基本思想:对于已按关键字排序的序列,经过一次比较,可将序列分割成两部分,然后只在有可能包含待查找元素的一部分中继续查找,并根据试探结果继续分割,逐步缩小查找范围,直到找到或找不到为止。选择排序的基本思想:每次从待排序序列中选择一个关键字最小的元素(当需要按关键字升序排列时),顺序排在己排序序列的最后,直至全部排完为止。堆积排序基本思想:1•堆积树的存储通常堆