实验3 归并排序分治策略的设计与实现
# include
# include
# define N 100
void Merge(int A[],int low,int mid,int heigh)
{// 将两个排好序的数组比较大小,按照从小到大的顺序寄存在b[]数组中int b[N],k = 0;
int l = low;
int h = mid+1;
while(l <= mid && h <= heigh)
{
if(A[l] < A[h])
{
b[k++] = A[l];
l++;
}
else
{
b[k++] = A[h];
h++;
}
}
if(l > mid)
{
while(h <= heigh)
{
b[k++] = A[h];
h++;
}
}
else
{
while(l <= mid)
{
b[k++] = A[l];
l++;
}
}
int j = low;
for(int i=0;i {// 将排好序的数组中的数复制到原来的A[]数组中去 A[j] = b[i]; j++; } } void M_sort(int A[],int low,int heigh) { int mid; if(low < heigh) {// 当low 小于heigh的时候,继续分治 mid = (low+heigh)/2; M_sort(A,low,mid); M_sort(A,mid+1,heigh); Merge(A,low,mid,heigh); } } void main() { /*freopen()函数的功能:简单说,就是实现重定向。 freopen("in.txt","r",stdin)的作用就是把stdin(标准输入)重定向到in.txt文件中, 这样在用scanf()输入时便不会从标准输入流提取数据,而是从in.txt文件中获取输入。 只要把输入数据事先粘贴到in.txt,调试时就方便多了。 freopen("out.txt","w",stdout)的作用就是把stdout(标准输出)重定向到out.txt文件中,使用printf()输出时便不会在屏幕显示了。*/ freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); int i,n; int A[N];// 储存要排序的数组 scanf("%d",&n);// 数据输入 for(i=0;i scanf("%d",&A[i]); M_sort(A,0,n-1);// 分治排序入口函数 for(i=0;i printf("%d ",A[i]); printf("\n"); } 排序算法 一、插入排序(Insertion Sort) 1. 基本思想: 每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止。 2. 排序过程: 【示例】: [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] Procedure InsertSort(Var R : FileType); //对R[1..N]按递增序进行插入排序, R[0]是监视哨// Begin for I := 2 To N Do //依次插入R[2],...,R[n]// begin R[0] := R[I]; J := I - 1; While R[0] < R[J] Do //查找R[I]的插入位置// begin R[J+1] := R[J]; //将大于R[I]的元素后移// J := J - 1 end R[J + 1] := R[0] ; //插入R[I] // end End; //InsertSort // 二、选择排序 1. 基本思想: 每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 2. 排序过程: 【示例】: 初始关键字[49 38 65 97 76 13 27 49] 第一趟排序后13 [38 65 97 76 49 27 49] 第二趟排序后13 27 [65 97 76 49 38 49] 第三趟排序后13 27 38 [97 76 49 65 49] 第四趟排序后13 27 38 49 [49 97 65 76] 第五趟排序后13 27 38 49 49 [97 97 76] 工作表中的排序 学习目标: 了解Excel在处理数据排序的原理;掌握和使用工作表排序的基本操作步骤和方法。 教学过程: 一、新课导入“ 在日常生活中,我们常常会将一些数据按大小不同,依次排序,以便人们做出比较、判断。这种情况下数据少的情况下我们可以迅速的做出判断和排序,但在数据繁杂的情况下就比较困难的比较出大小排列好顺序,这个时候我们就应该借助一些工具来完成。对于处理数据类的软件工具我们最常用的是Excel,下面我们就以某年意大利足球联赛的积分名次表为例,学习如何借助Excel来对数据进行排序。 二、精细操作 活动一:排序工具 1.单击Excel的菜单栏,找到“数据”选项,再找到“排序”这一工具。———(在此过程中先了解排序工具所在位置)并了解排序工具的含义如下图: 2.对需要排序的数据表大致要了解带着这几个问题: ①、数据表表头中包含哪些“关键字”例如:“积分”、“名次”“进球”等。 ②、我们需求是对那个“关键字”进行排序? ③、范围选择是哪些?排序是升序还是降序? 3.弄清上述问题,现在我们对“意大利足球联赛的积分名次表”中关键词“积分”栏进 行降序排序,具体操作如下: ⑴、用鼠标左键单击表格数据中任意一个单元格。 ⑵、在菜单栏的“数据”项中选取“排序”栏,按(如图)选择排序需要的选项。 ⑶、设置好的排序,点击确定按钮,得出以下排序表和原表对比(如图): 原 表 排 序 后 表 ⑷、在排序后的表格里名次所在列顺序有所变化,我们可以根据表格的“填充”功能把 顺序重新的填充(如图) 填充前填充后 活动二:保存 1、排序完成后需要对数据表保存具体操作: ⑴、单击文件(如图) ⑵、选好文档的格式,之后选择保存路径为桌面(如图) 活动三:练一练 通过电子表格排序功能对“学生成绩表”总分栏进行降序排序。 《数据结构》实验报告排序实验题目: 输入十个数,从插入排序,快速排序,选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路: 1. 插入排序:直接插入排序的基本操作是,将一个记录到已排好序的有序表中,从而得到一个新的,记录增一得有序表。 一般情况下,第i 趟直接插入排序的操作为:在含有i-1 个记录的有序子序列r[1..i-1 ]中插入一个记录r[i ]后,变成含有i 个记录的有序子序列r[1..i ];并且,和顺序查找类似,为了在查找插入位置的过程中避免数组下标出界,在r [0]处设置哨兵。在自i-1 起往前搜索的过程中,可以同时后移记录。整个排序过程为进行n-1 趟插入,即:先将序列中的第一个记录看成是一个有序的子序列,然后从第2 个记录起逐个进行插入,直至整个序列变成按关键字非递减有序序列为止。 2. 快速排序:基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 假设待排序的序列为{L.r[s] ,L.r[s+1],…L.r[t]}, 首先任意选取一个记录 (通常可选第一个记录L.r[s])作为枢轴(或支点)(PiVOt ),然后按下述原则重新排列其余记录:将所有关键字较它小的记录都安置在它的位置之前,将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置i 作为界线,将序列{L.r[s] ,… ,L.r[t]} 分割成两个子序列{L.r[i+1],L.[i+2], …,L.r[t]}。这个过程称为一趟快速排序,或一次划分。 一趟快速排序的具体做法是:附设两个指针lOw 和high ,他们的初值分别为lOw 和high ,设枢轴记录的关键字为PiVOtkey ,则首先从high 所指位置起向前搜索找到第一个关键字小于PiVOtkey 的记录和枢轴记录互相交换,然后从lOw 所指位置起向后搜索,找到第一个关键字大于PiVOtkey 的记录和枢轴记录互相 交换,重复这两不直至low=high 为止。 具体实现上述算法是,每交换一对记录需进行3 次记录移动(赋值)的操作。而实际上, 各种排序算法的总结和比较 1 快速排序(QuickSort) 快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快速排序可以由下面四步组成。 (1)如果不多于1个数据,直接返回。 (2)一般选择序列最左边的值作为支点数据。(3)将序列分成2部分,一部分都大于支点数据,另外一部分都小于支点数据。 (4)对两边利用递归排序数列。 快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法,但是就通常情况而言,没有比它更快的了。快速排序是递归的,对于内存非常有限的机器来说,它不是一个好的选择。 2 归并排序(MergeSort) 归并排序先分解要排序的序列,从1分成2,2分成4,依次分解,当分解到只有1个一组的时候,就可以排序这些分组,然后依次合并回原来的序列中,这样就可以排序所有数据。合并排序比堆排序稍微快一点,但是需要比堆排序多一倍的内存空间,因为它需要一个额外的数组。 3 堆排序(HeapSort) 堆排序适合于数据量非常大的场合(百万数据)。 堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录,因为快速排序,归并排序都使用递归来设计算法,在数据量非常大的时候,可能会发生堆栈溢出错误。 堆排序会将所有的数据建成一个堆,最大的数据在堆顶,然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆,交换数据,依次下去,就可以排序所有的数据。 Shell排序通过将数据分成不同的组,先对每一组进行排序,然后再对所有的元素进行一次插入排序,以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。 Shell排序比冒泡排序快5倍,比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相对比较简单,它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。 5 插入排序(InsertSort) 插入排序通过把序列中的值插入一个已经排序好的序列中,直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序,或者重复排序超过200数据项的序列。 比较好的岗位评价的基本方法 目前比较好的岗位评价方法有排序法、分类法、因素比较法、评分法 排序法是根据一些特定的标准(例如工作的复杂程度、对组织的贡献大小等对各个职位的相对价值)进行整体比较,进而将职位按照相对价值的高低排列出一个次序。其基本步骤是: 1、对排序的标准达成共识。虽然排序法是对岗位的整体价值进行评价而排序,但也需要参与评估的人员对什么样的“整体价值”更高达成共识,如责任更大,知识技能更高,工作更加复杂,环境因素恶劣等。 2、选定参与排序的职位。如果公司较小可以选取全部职位进行排序。 3、评定人员根据事先确定评判标准,对公司同类岗位的重要性逐一作出评判,最重要的排在第一位,次要的、再次要的顺次往下排列。 4、将经过所有评定人员评定的每个岗位的结果加以汇总,得到序号和。然后将序号和除以评定人数,得到每一岗位的平均序数。最后,按平均序数的大小,由小到大评定出各岗位的相对价值的次序。 分类法是在岗位分析的基础上,对组织中全部或规定范围内岗位进行多层次的划分,即先确定等级结构,然后再根据工作内容对工作岗位进行归类。其基本步骤是: 1、按照经营过程中各类岗位的作用和特征,将公司的全部岗位分成几个大的系统。 2、将各个系统中的各岗位分成若干层次,最少分为5-6档,最多的可分为15-20档。 3、明确规定各档次岗位的工作内容、责任和权限。 4、明确各系统各档次(等级)岗位的资格要求。 5、评定出不同系统不同岗位之间的相对价值和关系。 因素比较法是一种量化的工作评估方法,它实际上是对职位排序法的一种改进。这种方法选择多种报酬因素,按照各种因素分别进行排序。其基本步骤是: 1、选择基准岗位。选择一些在不同企业中普遍存在的、工作内容相对稳定的、具有得到公认的市场工资水平的职位做为基准岗位。 2、分析这些基准岗位,找出一系列共同的报酬因素。这些报酬因素应该是一些能够体现职位之间本质区别的因素。如责任、工作的复杂程度等。 3、将每个基准职位的工资分配到相应的报酬因素上。 4、将待评估的职位在每个报酬因素上分别与基准职位相比较,确定待评估职位在各个因素上的工资率。将待评估职位在各个报酬因素上的工资率或者分数相加汇总,得到待评估职位的工资水平。 评分法也称点数法,该法首先是选定岗位的主要影响因素,并采用一定点数(分值)表示每一因素,然后按预先规定的衡量标准,对现有岗位的各个因素逐一评比、估价,求得点数,经过加权求和,最后得到各个岗位的总点数。其基本步骤是: 1、确定岗位评价的主要因素。四个方面:责任因素,知识技能因素,岗位性质因素,环境因素。并确定主要因素的权重。 2、对各评价因素区分出不同档别,并赋予一定的点数(分值)。 3、对各岗位进行评价。对各岗位每一因素打分,然后汇总,计算出各岗位的总点数。 4、根据各岗位的总点数进行排序,得到相对价值的高低。 上述各种方法之间有一定传承关系,目前,评分法是岗位评价的主流方法。如果需要评价的岗位数很少,前三种方法倒也不失为简单可行的选择。 《排序问题求解》实验报告 一、算法的基本思想 1、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中,从而得到一个新的, 记录数增1 的有序序列。 直接插入排序算法的伪代码称为InsertionSort,它的参数是一个数组A[1..n],包含了n 个待排序的数。用伪代码表示直接插入排序算法如下: InsertionSort (A) for i←2 to n do key←A[i] //key 表示待插入数 //Insert A[i] into the sorted sequence A[1..i-1] j←i-1 while j>0 and A[j]>key do A[j+1]←A[j] j←j-1 A[j+1]←key 2、快速排序算法思想 快速排序算法的基本思想是,通过一趟排序将待排序序列分割成独立的两部分,其中一 部分记录的关键字均比另一部分记录的关键字小,则可对这两部分记录继续进行排序,以达到整个序列有序。 假设待排序序列为数组A[1..n],首先选取第一个数A[0],作为枢轴(pivot),然后按照下述原则重新排列其余数:将所有比A[0]大的数都排在它的位置之前,将所有比A[0]小的数都排在它的位置之后,由此以A[0]最后所在的位置i 作为分界线,将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序,对子数组A[1..i-1]和A[i+1..n]排序。 一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey,则首先从high 所指位置起向前搜索,找到第一个小于pivotkey 的数,并将其移到低端,然后从low 所指位置起向后搜索,找到第一个大于pivotkey 的数,并将其移到高端,重复这两步直至low=high。最后,将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下: Partition ( A, low, high) A[0]←A[low] //用数组的第一个记录做枢轴记录 privotkey←A[low] //枢轴记录关键字 while low 算法分析与设计习题集整理 第一章算法引论 一、填空题: 1、算法运行所需要的计算机资源的量,称为算法复杂性,主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征:输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣:时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为: O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法:自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求:正确性 和 可读性。 8、计算下面算法的时间复杂度记为: O(n 2) 。 for (i =1;i 信息学部算法分析 上机报告 学号0901******** 姓名陈龙 指导老师秦明 时间2011.11.1~11.23 一.上机实验题目 实验1 比较归并排序和快速排序的区别。 实验2 利用贪心算法对背包问题进行求解。 二.算法设计思路 归并排序: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列,设定两个指针,最初位置分别为两个已经排序序列的起始位置,比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置,重复步骤直到某一指针达到序列尾,将另一序列剩下的所 有元素直接复制到合并序列尾。 快速排序: 设置两个变量I、J,排序开始的时候:I=0,J=N-1;以第一个数组元素作为关键数据,赋值给key,即key=A[0];从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于key的值A[J],并与key交换;从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于key的A[I],与key交换;重复第3、4、5步,直到I=J;(3,4步是在程序中没找到时候j=j-1,i=i+1,直至找到为止。找到并交换的时候i,j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。) 背包问题: 用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 。可以压缩空间,f[v]=max{f[v],f[v-c[i]]+w[i]} 三. 源程序 归并排序 #include 常见内部排序算法比较 排序算法是数据结构学科经典的内容,其中内部排序现有的算法有很多种,究竟各有什么特点呢?本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序,直接插入排序,简单选择排序,快速排序,堆排序,针对关键字的比较次数和移动次数进行测试比较。 问题分析和总体设计 ADT OrderableList { 数据对象:D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0} 数据关系:R1={〈ai-1,ai〉|ai-1, ai∈D, i=1,2,…,n} 基本操作: InitList(n) 操作结果:构造一个长度为n,元素值依次为1,2,…,n的有序表。Randomizel(d,isInverseOrser) 操作结果:随机打乱 BubbleSort( ) 操作结果:进行起泡排序 InserSort( ) 操作结果:进行插入排序 SelectSort( ) 操作结果:进行选择排序 QuickSort( ) 操作结果:进行快速排序 HeapSort( ) 操作结果:进行堆排序 ListTraverse(visit( )) 操作结果:依次对L种的每个元素调用函数visit( ) }ADT OrderableList 待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果. 要求对结果进行分析. 详细设计 1、起泡排序 算法:核心思想是扫描数据清单,寻找出现乱序的两个相邻的项目。当找到这两个项目后,交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。 bubblesort(struct rec r[],int n) { int i,j; struct rec w; unsigned long int compare=0,move=0; for(i=1;i<=n-1;i++) for(j=n;j>=i+1;j--) { if(r[j].key 电子科技大学实验报告 课程名称:数据结构与算法 学生姓名: 学号: 点名序号: 指导教师: 实验地点:基础实验大楼 实验时间: 5月20日 2014-2015-2学期 信息与软件工程学院各种排序算法比较
工作表中的排序教案
《数据结构》实验报告——排序.docx
各种排序算法的总结和比较
岗位评价方法有排序法 Word 2007 文档
算法排序问题实验报告
算法分析与设计习题集整理
排序算法比较实验报告
几种常见内部排序算法比较
实验报告-排序与查找