当前位置:首页 > 商业/管理/HR > 信息化管理 > 数据结构课程设计报告(各种排序实现及对比)
数据结构课程设计报告设计题目:学生姓名:系别:专业:班级:学号:指导教师:2010年版2目录一、设计题目……………………………………………………4二、运行环境(软、硬件环境)………………………………4三、算法设计的思想……………………………………………43.1简单选择排序………………………………………………43.2直接插入排序……………………………………………….43.3希尔排序……………………………………………………43.4冒泡排序……………………………………………………43.5快速排序……………………………………………………4四、算法的流程图……………………………………………….54.1主函数的算法流程图………………………………………...5.4.2简单选择排序的算法流程图………………………………….64.3直接插入排序的算法流程图………………………………….74.4希尔排序的算法流程图………………………………………84.5冒泡排序的算法流程图………………………………………94.6快速排序的算法流程图(1)………………………………..104.7快速排序的算法流程图(2)………………………………..11五、算法设计分析………………………………………………115.1简单选择排序………………………………………………115.2直接插入排序……………………………………………….125.3希尔排序……………………………………………………125.4冒泡排序……………………………………………………135.5快速排序……………………………………………………13六、源代码………………………………………………………14七、运行结果分析………………………………………………23八、收获及体会…………………………………………………263一、设计题目各种排序二、运行环境(软、硬件环境)软件环境:操作系统的名称windows、版本号XP;程序开发的环境:MicrosoftVisualC++6.0硬件环境:内存:512M,硬盘:80G三、算法设计的思想3.1简单选择排序1基本思想每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列的第i个关键字。3.2插入排序1基本思想插入排序的思想就是读一个,排一个,将第1个数放入数组的第1个元素中,以后读入的数与已存入数组的数进行比较,确定它在从大到小的排列中应处的位置.将该位置以及以后的元素向后推移一个位置,将读入的新数填入空出的位置中.3.3希尔排序1基本思想希尔排序法是1959年由D.L.Shell提出来的,又称减少增量的排序。下表是以八个元素排序示范的例子.在该例中,开始时相隔4个成分,分别按组进行排序,这时每组2个成分,共4组;然后相隔2个成分,在按组排序......最后,对所有相邻成分进行排序.3.4冒泡排序1基本思想依次比较相邻的两个数,把大的放前面,小的放后面.即首先比较第1个数和第2个数,大数放前,小数放后.然后比较第2个数和第3个数......直到比较最后两个数.第一趟结束,最小的一定沉到最后.重复上过程,仍从第1个数开始,到最后第2个数.然后......由于在排序过程中总是大数往前,小数往后,相当气泡上升,所以叫冒泡排序.3.5快速排序1基本思想快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r],如果规模足够小则直接进行排序,否则分三步处理:402135467ny分解(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]就已排好序。四、算法的流程图4.1主函数的算法流程图开始输入数据个数lengthcreate(),visit()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);输入select输入y/n结束54.2简单选择排序的算法流程图假假真真真假开始iL.lengthkL.lenthL.r[j].keyL.r[k].keyi!=j结束j=k;intj=i;k=i+1inti=1;k++L.r[i]L.r[j]i++64.3直接插入排序的算法流程图真真假假真假开始i=2i=L.lengthL.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结束74.4希尔排序的算法流程图假真真真假假真假开始k=0i=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结束ktShellInsert(&L,dlta[k],&r);i=dk+1;++k84.5冒泡排序的算法流程图假假假真真真开始inti=1;iL.lengthintj=1;jL.length-iL.r[j].keyL.r[j+1].keyL.r[j]L.r[j+1]结束j++i++94.6快速排序的算法流程图(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=pivotkey77104.7快速排序的算法流程图(2)五、算法设计分析5.1简单选择排序操作方法:第一趟,从n个记录中找出关键码最小的记录与第一个记录交换;第二趟,从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录交换;如此,第i趟,则从第i个记录开始的n-i+1个记录中选出关键码最小的记录与第i个记录交换,直到整个序列按关键码有序。真假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【效率分析】空间效率:仅用了一个辅助单元。时间效率:简单选择排序中,所需进行记录移动的操作次数较小,其最小值为0,最大值为3(n-1)。然而,无论记录的初始排列如何,所需进行的关键字之间的比较次数相同,均为n(n-1)/2。因此,总的时间复杂度也是O(n2)。5.2直接插入排序设有n个记录,存放在数组r中,重新安排记录在数组中的存放顺序,使得按关键码有序。即r[1].key≤r[2].key≤……≤r[n].key先来看看向有序表中插入一个记录的方法:设1j≤n,r[1].key≤r[2].key≤……≤r[j-1].key,将r[j]插入,重新安排存放顺序,使得r[1].key≤r[2].key≤……≤r[j].key,得到新的有序表,记录数增1。【效率分析】空间效率:仅用了一个辅助单元。时间效率:向有序表中逐个插入记录的操作,进行了n-1趟,每趟操作分为比较关键码和移动记录,而比较的次数和移动记录的次数取决于待排序列按关键码的初始排列。最好情况下:即待排序列已按关键码有序,每趟操作只需1次比较2次移动。总比较次数=n-1次总移动次数=2(n-1)次最坏情况下:即第j趟操作,插入记录需要同前面的j个记录进行j次关键码比较,移动记录的次数为j+2次。平均情况下:即第j趟操作,插入记录大约同前面的j/2个记录进行关键码比较,移动记录的次数为j/2+2次。由此,直接插入排序的时间复杂度为O(n2)。是一个稳定的排序方法5.3希尔排序(Shell’sSort)直接插入排序算法简单,在n值较小时,效率比较高,在n值很大时,若序列按关键码基本有序,效率依然较高,其时间效率可提高到O(n)。希尔排序即是从这两点出发,给出插入排序的改进方法。希尔排序方法:1.选择一个步长序列t1,t2,…,tk,其中titj,tk=1;2.按步长序列个数k,对序列进行k趟排序;3.每趟排序,根据对应的步长ti,将待排序列分割成若干长度为12m的子序列,分别对各子表进行直接插入排序。仅步长因子为1时,整个序列作为一个表来处理,表长度即为整个序列的长度。希尔排序时效分析很难,关键码的比较次数与记录移动次数依赖于步长因子序列的选取,特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的步长因子序列的方法。步长因子序列可以有各种取法,有取奇数的,也有取质数的,但需要注意:步长因子中除1外没有公因子,且最后一个步长因子必须为1。希尔排序方法是一个不稳定的排序方法。5.4冒泡排序冒泡排序方法:对n个记录的表,第一趟冒泡得到一个关键码最大的记录r[n],第二趟冒泡对n-1个记录的表,再得到一个关键码最大的记录r[n-1],如此重复,直到n个记录按关键码有序的表。【效率分析】空间效率:仅用了一个辅助单元。时间效率:总共要进行n-1趟冒泡,对j个记录的表进行一趟冒泡需要j-1次关键码比较。移动次数:最好情况下:待排序列已有序,不需移动。5.5快速排序快速排序是通过比较关键码、交换记录,以某个记录为界(该记录称为支点),将待排序列分成两部分。其中,一部分所有记录的关键码大于等于支点记录的关键码,另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程,称为一次划分。对各部分不断划分,直到整个序列按关键码有序。【效率分析】空间效率:快速排序是递归的,每层递归调用时的指针和参数均要用栈来存放,递归调用层次数与上述二叉树的深度一致。因而,存储开销在理想情况下为O(log2n),即树的高度;在最坏情况下,即二叉树是一个单链,为O(n)。时间效率:在n个记录的待排序列中,一次划分需要约n次关键码比较,时效为O(n),若设T(n)为对n个记录的待排序列进行快速排序所需时间。理想情况下:每次划分,正好将分成两个等长的子序列,则T(n)≤cn+2T(n/2)c是一个常数13≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)≤2cn+4(cn/4+T(n/8))=3cn+8T(n/8)······≤cnlog2n+nT(1)=O(nlog2n)最坏情况下:即每次划分,只得到一个子序列,时效为O(n2)。快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时,快排序反而蜕化为冒泡排序。为改进之,通常以“三者取中法”来选取支点记录,即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。内部排序各种算法的性能比较(表)六、源代码#includestdlib.h#includestdio.h#includetime.h#defineMAXSIZE200typedefintKeyType;type
本文标题:数据结构课程设计报告(各种排序实现及对比)
链接地址:https://www.777doc.com/doc-4924962 .html