综合排序正式论文

第1页共38页目录一、问题描述.........................................................................................................................12.1基本要求：......................................................................................................................12.2.算法思想：.....................................................................................................................12.3.模块划分：.....................................................................................................................32.4.数据结构：...................................................................................................................182.5.源程序：.......................................................................................................................192.6.测试情况：...................................................................................................................30三、小结.......................................................................................................................................37四、参考文献...............................................................................................................................38一、问题描述用C语言编程解决插入、冒泡，快速排序，简单选择，堆排序以及分析各种算法的时间复杂度和空间复杂度，比较各种排序在不同场合的适用程度，分析各种排序算法的实用性。内容简介2.1基本要求：（1）设计一个的菜单将在实现的功能显示出来，并有选择提示；（2）分别实现直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序，堆排序算法；（3）通过多种测试数据，对各种排序算法的时间复杂度和空间复杂度进行比较2.2.算法思想：2.2.1简单选择排序1基本思想每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列的第i个关键字。2.2.2直接插入排序1基本思想插入排序的思想就是读一个，排一个，将第１个数放入数组的第１个元素中，以后读入的数与已存入数组的数进行比较，确定它在从大到小的排列中应处的位置．将该位置以及以后的元素向后推移一个位置，将读入的新数填入空出的位置中．第2页共38页2.2.3折半插入排序1基本思想从第二个数开始逐个置入监视哨，使用low，high标签进行折半判断比较大小，并确认插入位置，该位置到最后一个数全部后移一位，最后腾出该位置，把监视哨里面的数置入该位置。后面的数以此类推进行排序，直到最后一个数比较完毕。2.2.4希尔排序1基本思想希尔排序法是1959年由D.L.Shell提出来的,又称减少增量的排序。下表是以八个元素排序示范的例子.在该例中,开始时相隔4个成分,分别按组进行排序,这时每组2个成分,共4组;然后相隔2个成分,在按组排序......最后,对所有相邻成分进行排序.2.2.5冒泡排序1基本思想依次比较相邻的两个数,把大的放前面,小的放后面.即首先比较第1个数和第2个数,大数放前,小数放后.然后比较第2个数和第3个数......直到比较最后两个数.第一趟结束,最小的一定沉到最后.重复上过程,仍从第1个数开始,到最后第2个数.然后......由于在排序过程中总是大数往前,小数往后,相当气泡上升,所以叫冒泡排序.2.2.6快速排序1基本思想快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。2.2.7堆排序1基本思想堆排序，顾名思义，就是基于堆。因此先来介绍一下堆的概念。堆分为最大堆和最小堆，其实就是完全二叉树。大顶堆要求节点的元素都要大于其孩子，小顶堆要求节点元素都小于其左右孩子，两者对左右孩子的大小关系不做任何要求。有了第3页共38页上面的定义，我们可以得知，处于大顶堆的根节点的元素一定是这个堆中的最大值。其实我们的堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆，依次类推，最终得到排序的序列。或者说，堆排序将所有的待排序数据分为两部分，无序区和有序区。无序区也就是前面的最大堆数据，有序区是每次将堆顶元素放到最后排列而成的序列。每一次堆排序过程都是有序区元素个数增加，无序区元素个数减少的过程。当无序区元素个数为1时，堆排序就完成了。本质上讲，堆排序是一种选择排序，每次都选择堆中最大的元素进行排序。只不过堆排序选择元素的方法更为先进，时间复杂度更低，效率更高。2.3.模块划分：2.3.1主函数的算法功能描述开始输入数据个数lengthcreate(),visit()输入select第4页共38页02135467ny782.3.2退出函数：exit();功能描述：根据提示输入0，则退出系统2.3.3选择排序算法功能描述函数：select_sort();BinsertSort()selectExit(0)select_sort(L);Zhijie(L)ShellSort()Maopao(L);QuickSort(L);select_sort(L);Zhijie(L);ShellSort(L,dlta,4);Maopao(L);QuickSort(L);print(num);输入y/n结束HeapSort()假开始iL.lengthinti=1;第5页共38页2.3.4直接插入排序算法描述假假真真真kL.lenthL.r[j].keyL.r[k].keyi!=j结束j=k;intj=i;k=i+1k++L.r[i]L.r[j]i++假开始i=2i=L.length第6页共38页2.3.5希尔排序算法功能描述真真假假真L.r[i].keyL.r[i-1].keyL.r[0]=L.r[i]；L.r[i]=L.r[i-1]；j=i-2；L.r[0].keyL.r[j].keyL.r[j+1]=L.r[j]；--j；L.r[j+1]=L.r[0]++i结束假开始k=0kt第7页共38页2.3.6冒泡算法功能描述真真真假假真假i=L.lengthL.r[i].keyL.r[i-dk].keyL.r[0]=L.r[i]；j=i-dk；j0&&L.r[0].keyL.r[j].keyL.r[j+dk]=L.r[j]；j-=dk；L.r[j+dk]=L.r[0]++i结束ShellInsert(&L,dlta[k],&r);i=dk+1;++k第8页共38页假假假真真真开始inti=1;iL.lengthintj=1;jL.length-iL.r[j].keyL.r[j+1].keyL.r[j]L.r[j+1]结束j++i++第9页共38页2.3.7快速排序算法功能描述1算法功能描述真L.r[0]=L.r[low]Pivotkey=L.r[low].keyL,low,highLowhighL.r[low]=L.r[high]Lowhigh&&L.r[high].key=pivotkey++lowL.r[high]=L.r[low]--high结束真假假真假开始Lowhigh&&L.r[high].key=pivotkey77第10页共38页2算法描述真假L，low，highLowhighPivotloc=partioion(L,low,high),low=low,high=pivotloc-1;L,low=pivotloc+1,high=highLowhighPivotloc=partioion(L,low,high),low=low,high=pivotloc-1;QSort(L,low,pivotloc-1)真假开始结束第11页共38页2.3.8堆排序1调整为大顶堆开始j=2*sj=mL.r[s]=rcj*=2jm&&L.r[j].keyL.r[j+1].key++jL.r[s]=L.r[j];s=j;rc.key=L.r[j].key结束L、rc、mrc=L.r[s]第12页共38页2堆排序开始i=L.length/2i0--i；HeapAdjust(L,i,L.length)；r.comp++;是i1r.comp++;L.r[1]←→L.r[i];r.move=r.move+3;i!=1r.compex++;t=L.r[1];L.r[1]=L.r[i];L.r[i]=t;r.move=r.move+3;HeapAdjust(L,1,i-1);否是结束第13页共38页第14页共38页2.3.9折半插入排序第15页共38页开始i=2,j,high,low,m;i=L.lengthL.r[0]=L.r[i];是low=highr.comx++;r[low..high]m=(low+high)/2;是L.r[0].keyL.r[m].keyhigh=m-1;r.move++;r.comp++;low=m+1;r.move++;r.comp++;j=i-1j=high+1;--j；L.r[j+1]=L.r[j];是L.r[high+1]=L.r[0];结束否是否否否第16页共38页2.3.10打印函数voidvisit(SqListL)：打印链表中的数据第17页共38页输入序排序个数（小于200）create(&L,length);visit(L);输入Select（0-8）输入0退出输入1select_sort(L);输入2Zhijie(L);输入6HeapSort(L);输入7BInsertSort(L);输入8flag=1;select_sort(L)Zhijie(L);ShellSortMaopao(L);QuickSort(L);print(num);flag=0;getchar();c=getchar();c=='n'||c=='N'结束开始输入3ShellSort(L,dlta,5);输入4Maopao(L