16 分配和归并排序

排序算法比较实验报告

信息学部算法分析 上机报告 学号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 #include # define N 50 int b[N],a[N]; int n,i; void Merge (int low, int mid,int high) //合并 { int i; int l=low,h=mid+1,k=l; while ((l<=mid) && (h<=high)) //部分合并 { if (a[l]<=a[h]) b[k++]=a[l++]; else b[k++]=a[h++]; } if(l>mid) while (h<=high) b[k++]=a[h++]; //转储剩余部分 else while(l<=mid) b[k++]=a[l++]; for (i=0;i<=high;i++) //将b数组转储到a a[i]=b[i]; } int Merge2 (int l,int h) //分类 { for (i=0;i

简单的归并排序算法例子

import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.Random; public class GuiBing { public static void main(String[] args) throws Exception { int datalength=1000000; GuiBing gui=new GuiBing(); int[] array1=gui.createArray(datalength); int[] array2=gui.createArray(datalength); Thread.sleep(20000); long startTime = System.nanoTime();//纳秒精度 long begin_freeMemory=Runtime.getRuntime().freeMemory(); int[] final_array=gui.guibing(array1,array2); boolean result=gui.testResult(final_array); long end_freeMemory=Runtime.getRuntime().freeMemory(); System.out.println("result===="+result); long estimatedTime = System.nanoTime() - startTime; System.out.println("elapsed time(纳秒精 度):"+estimatedTime/100000000.0); System.out.println("allocated memory:"+(begin_freeMemory-end_freeMemory)/1000.0+" KB"); Thread.sleep(20000); } /** * 显示数组的内容 * @param array */ private static void dispalyData(int[] array) { for(int i=0;i

数据结构课程设计排序实验报告

《数据结构》课程设计报告 专业 班级 姓名 学号 指导教师 起止时间

课程设计：排序综合 一、任务描述 利用随机函数产生n个随机整数（20000以上），对这些数进行多种方法进行排序。（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 （2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 要求：根据以上任务说明，设计程序完成功能。 二、问题分析 1、功能分析 分析设计课题的要求，要求编程实现以下功能： （1）随机生成N个整数，存放到线性表中； （2）起泡排序并计算所需时间； （3）简单选择排序并计算时间； （4）希尔排序并计算时间； （5）直接插入排序并计算所需时间； （6）时间效率比较。 2、数据对象分析 存储数据的线性表应为顺序存储。 三、数据结构设计 使用顺序表实现，有关定义如下： typedef int Status; typedef int KeyType ; //设排序码为整型量 typedef int InfoType; typedef struct { //定义被排序记录结构类型 KeyType key ; //排序码 I nfoType otherinfo; //其它数据项 } RedType ; typedef struct { RedType * r; //存储带排序记录的顺序表 //r[0]作哨兵或缓冲区 int length ; //顺序表的长度 } SqList ; //定义顺序表类型 四、功能设计 （一）主控菜单设计

算法设计实验一归并排序(分治)和插入排序的比较分析

沈阳化工大学实验报告 课程名称算法设计与分析 项目名称归并排序(分治)和插入排序的比较 学院应用技术学院 专业计中职1401 指导教师张雪 报告人张庭浩学号 1422030125 实验时间 2016.11.05 提交时间 2016.11.05

一、实验目的 1.理解和掌握分治算法的相关内容。 2.具体完成插入排序和归并排序性能的比较。 二、实验内容 编写一个真随机函数，随机产生大量数字。在产生相同的一组大量随机数字后，分别用归并排序和插入排序两种算法进行排序，并通过时间函数分别计算出运行的时间。 三、伪代码 1.归并排序 /*数组a[]是原始数组，数组b[]是目标数组*/ 归并排序（数组a[],数组b[]）{ `分割与归并（数组a[],0, a.length,数组b[]) } /*通过递归把要排序的子序列分的足够小*/ 分割与归并（数组a[],起始位置,结束位置,数组b[]){ if(结束位置- 起始位置< 2) 返回 中间位置= （起始位置+结束位置）/2 分割与归并（数组a[],起始位置,中间位置,数组b[]) 分割与归并（数组a[],中间位置,结束位置,数组b[]) 归并（数组a[],起始位置，中间位置，结束位置，数组b[]) 拷贝（数组a[],起始位置，结束位置，数组b[]) } 归并（数组a[],起始位置，中间位置，结束位置，数组b[]){ i0 = 起始位置，i1 = 中间位置 for j = 起始位置到结束位置 if(i0 < 中间位置且（i1 > 结束位置或a[i0] <= a[i1]){ //当i0没有超过中间位置时，有两种情况要将a[i0]复制到b[j]上： //1.i1已经超过结束位置，只要把剩下的复制过来就好； //2.a[i0]比a[i1]小 b[j]=a[i0] i0++ } else { b[j]=a[i1] i1++ } }

归并排序算法实现 (迭代和递归)

归并排序算法实现（迭代和递归）\递归实现归并排序的原理如下： 递归分割: 递归到达底部后排序返回: 最终实现排序： #include void merge(int *array, int low, int center, int high) { if(low >= high) return; int m = center - low + 1; int n = high - center; int L[m], R[n]; for(int i=0; i R[j]) array[k] = R[j++]; else array[k] = L[i++];

} while(i #include

排序问题实验报告

2010级数据结构实验报告 实验名称：排序 姓名：袁彬 班级： 2009211120 班内序号： 09 学号： 09210552 日期： 2010 年12 月19 日 1．实验要求 试验目的： 通过选择试验内容中的两个题目之一，学习、实现、对比各种排序的算法，掌握各种排序算法的优缺点，以及各种算法使用的情况。 试验内容： 题目一： 使用简单数组实现下面各种排序算法，并进行比较。 排序算法如下： ①插入排序； ②希尔排序 ③冒泡排序； ④快速排序； ⑤简单选择排序； ⑥堆排序 ⑦归并排序 ⑧基数排序 ⑨其他。 具体要求如下： ①测试数据分为三类：正序，逆序，随机数据。 ②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。 ③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。 ④对②和③的结果进行分析，验证上述各种算法的时间复杂度。 ⑤编写main()函数测试各种排序算法的正确性。 题目二： 使用链表实现下面各种排序算法，并进行比较。 排序算法如下： ①插入排序； ②冒泡排序； ③快速排序；

④简单选择排序； ⑤其他。 具体要求如下： ①测试数据分为三类：正序，逆序，随机数据。 ②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。 ③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙（选作） ④对②和③的结果进行分析，验证上述各种算法的时间复杂度。 ⑤编写main()函数测试各种排序算法的正确性。 2. 程序分析 2.1 存储结构 程序中每一个算法均是用一个类来表示的，类中有自己的构造函数、排序函数。 程序的储存结构采用数组。数组的第一个位置不存储数据。数据从第二个位置开始。数组中的相对位置为数组的下标。 2.2 关键算法分析 ㈠、关键算法： 1、插入排序函数：Insert s ort(int n) ①、从2开始做循环，依次和前面的数进行比较：for(int i=2;i<=n;i++) ②、如果后面的比前面的小，则进行前移：if(number[i]=1;d=d/2) ②、在自己的间隔中进行简单插入排序，进行循环：for(int i=d+1;i<=n;i++) ③、如果后面的数据比前面的小，进行前移：if(number[i]0;j=j-d) ⑥、大的数据后移：number[j+d]=number[j]; ⑦、哨兵归位：number[j+d]=number[0]; 3、冒泡排序函数：Bubble s ort(int n) ①、设置有序无序的边界点：int pos=n; ②、当边界点不为空进行循环：while(pos!=0) ③、边界点传递给bound：int bound=pos; ④、从开始到边界点进行循环：for(int i=1;inumber[i+1]) ⑥、交换：number[0]=number[i];number[i]=number[i+1];number[i+1]=number[0]; ⑦、从小设置边界点：pos=i; 4、一趟快速排序函数：partion(int first,int end) ①、传递设置整个数据的起点和终点：int i=first;int j=end; ②、设置中轴：number[0]=number[i]; ③、当end大于first进行循环：while(i

多种排序的并行算法(具体)

1 排序 排序是数据处理中经常使用的一种重要运算，如何进行排序，特别是如何进行高效的排序，是计算机应用中的重要课题。排序的对象一般是一组记录组成的文件，而记录则是由若干数据项组成，其中的一项可用来标志一个记录，称为关键字项，该数据项的值称为关键字。所谓排序，就是要整理文件中的记录，使得它按关键字递增（或递减）的次序排列起来。若给定的文件含有n个记录｛R1，R2，…，R n｝，它们的关键字分别为｛K1，K2，…，K n｝，要把这n个记录重新排列成为｛R i1，R i2，…，R in｝，使得｛K i1≥K i2≥…≥K in｝（或｛K i1≤K i2≤…≤K in｝）。 本章主要介绍了枚举排序、快速排序、PSRS排序算法以及它们的MPI编程实现。1.1 枚举排序 1.1.1 枚举排序及其串行算法 枚举排序（Enumeration Sort）是一种最简单的排序算法，通常也称为秩排序（Rank Sort）。该算法的具体思想是（假设按关键字递增排序），对每一个待排序的元素统计小于它的所有元素的个数，从而得到该元素最终处于序列中的位置。假定待排序的n个数存在a[1]…a[n]中。首先将a[1]与a[2]…a[n]比较，记录比其小的数的个数，令其为k，a[1]就被存入有序的数组b[1]…b[n]的b[k+1]位置上；然后将a[2]与a[1]，a[3]…a[n]比较，记录比其小的数的个数，依此类推。这样的比较操作共n(n-1)次，所以串行秩排序的时间复杂度为O（n2）。 算法13.1 枚举排序串行算法 输入：a[1]…a[n] 输出：b[1]…b[n] Begin for i=1 to n do (1) k=1 (2) for j=1 to n do if a[i]>a[j] then k=k+1 end if end for (3) b[k]= a[i] end for End 1.1.2 枚举排序的并行算法 对该算法的并行化是很简单的，假设对一个长为n的输入序列使用n个处理器进行排序，只需是每个处理器负责完成对其中一个元素的定位，然后将所有的定位信息集中到主进程中，由主进程负责完成所有元素的最终排位。该并行算法描述如下： 算法13.2 枚举排序并行算法

各种排序实验报告

【一】需求分析 课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。 为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。 【二】概要设计 1.堆排序 ⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。 ⑵程序实现及核心代码的注释： for(j=2*i+1; j<=m; j=j*2+1) { if(j=su[j]) break; su[i]=su[j]; i=j; } su[i]=temp; } void dpx() //堆排序 { int i,temp; cout<<"排序之前的数组为："<=0; i--) { head(i,N); } for(i=N-1; i>0; i--) {

temp=su[i]; su[i]=su[0]; su[0]=temp; head(0,i-1); } cout<<"排序之后的数组为："<

数据结构实验四题目一排序实验报告

数据结构实验报告 实验名称：实验四——排序 学生：XX 班级： 班序号： 学号： 日期： 1．实验要求 实验目的： 通过选择实验容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 题目1： 使用简单数组实现下面各种排序算法，并进行比较。 排序算法如下： 1、插入排序； 2、希尔排序； 3、冒泡排序； 4、快速排序； 5、简单选择排序； 6、堆排序； 7、归并排序； 8、基数排序（选作）； 9、其他。 具体要求如下： 1、测试数据分成三类：正序、逆序、随机数据。 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关 键字交换记为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。 5、编写main（）函数测试各种排序算法的正确性。 2. 程序分析 2.1 存储结构

存储结构：数组 2.2 关键算法分析 一、关键算法： 1、插入排序 a、取排序的第二个数据与前一个比较 b、若比前一个小，则赋值给哨兵 c、从后向前比较，将其插入在比其小的元素后 d、循环排序 2、希尔排序 a、将数组分成两份 b、将第一份数组的元素与哨兵比较 c、若其大与哨兵，其值赋给哨兵 d、哨兵与第二份数组元素比较，将较大的值赋给第二份数组 e、循环进行数组拆分 3、对数据进行编码 a、取数组元素与下一个元素比较 b、若比下一个元素大，则与其交换 c、后移，重复 d、改变总元素值，并重复上述代码 4、快速排序 a、选取标准值 b、比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后 指针前移，重新比较 c、否则后面元素赋给前面元素 d、若后指针元素小于标准值，前指针后移，重新比较 e、否则前面元素赋给后面元素 5、简单选择排序 a、从数组中选择出最小元素 b、若不为当前元素，则交换 c、后移将当前元素设为下一个元素 6、堆排序 a、生成小顶堆 b、将堆的根节点移至数组的最后 c、去掉已做过根节点的元素继续生成小顶堆

并行归并排序

串行归并与并行归并排序算法 一、串行归并排序算法 归并排序是一种很容易进行并行化的算法，因为归并的各个数据区间都是独立的，没有依赖关系。并且归并排序是一种速度比较快的排序，且是一种稳定的排序算法，排序速度与关键词初始排列无关。 串行归并排序的算法大体的可以描述为：首先将要排序的表分成两个节点个数基本相等的子表，然后对每个子表进行排序，最后将排好序的两个子表合并成一个子表。在对子表进行排序时可以将子表再分解成两个节点数量基本相同的子表，当子表足够小时，也可以采用其他排序方法对子表进行排序，然后再对排好序的子表进行归并操作，最后将整个表排好序。 1、1算法流程图 并行归并排序算法的流程图： 串行归并排序算发流程图

1、2代码分析 #include using namespace std; #define N 11 int array[N] = { 4, 67, 456, 23, 1, 78, 26, 222, 34, 432, 12 }; //待排序数组int other[N]; //辅助空间,用以暂存已经排序的数组元素 void Swap(int &a, int &b) { int tmp = a; a = b; b = tmp; } /* array 待排序数组 * begin 数组开始的下标 * end 数组最后一个元素的下标 */ void MergeSort(int *array, int begin, int end) { if(end-begin+1 > 2) { MergeSort(array, begin, (end+begin)/2); MergeSort(array, (end+begin)/2+1, end); int i = begin, j = (end+begin)/2+1, k=begin; while(i<=(begin+end)/2 && j<=end) { if(array[i] < array[j]) other[k++] = array[i++]; else other[k++] = array[j++]; } while(i <= (begin+end)/2) other[k++] = array[i++]; while(j <= end) other[k++] = array[j++]; for(k=begin; k<=end; ++k) array[k] = other[k]; } else

数据结构各种排序实验报告

目录 1.引言............................................................................................................................ 错误！未定义书签。 2.需求分析 (2) 3.详细设计 (2) 3.1 直接插入排序 (2) 3.2折半排序 (2) 3.3 希尔排序 (4) 3.4简单选择排序 (4) 3.5堆排序 (4) 3.6归并排序 (5) 3.7冒泡排序 (7) 4.调试 (8) 5.调试及检验 (9) 5.1 直接插入排序 (9) 5.2折半插入排序 (9) 5.3 希尔排序 (10) 5.4简单选择排序 (10) 5.5堆排序 (11) 5.6归并排序 (12) 5.7冒泡排序 (12) 6.测试与比较................................................................................................................ 错误！未定义书签。 6.1调试步骤......................................................................................................... 错误！未定义书签。 6.2结论 (13) 7.实验心得与分析 (13) 8.附录 (15) 8.1直接插入排序 (15) 8.2折半插入排序 (16) 8.3希尔排序 (18) 8.4简单选择排序 (20) 8.5堆排序 (21) 8.6归并排序 (24) 8.7冒泡排序 (27) 8.8主程序 (28)

多路归并排序 外部排序算法

关于多路归并排序外部排序败者树技术积累2009-11-24 21:52:06 阅读453 评论0 字号：大中小 编程珠玑第一个case是有关一个技巧性解决外部排序问题的。问题很巧妙的解决了，但一开始提到的利用归并排序进行外部排序的算法仍值得仔细探究一下，毕竟本科时学的不是很深入。 先来看内部排序中最简单的2路归并排序算法。 算法核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列，给定数组中序列界限i、m、n，用2个下标变量分别从i和j=m+1开始逐个往后处理，先比较，小的写到结果序列的当前遍历下标k中，相应下标自增继续比较直到某个序列的下标走到边界，再将另外一个序列的剩余元素拷贝到结果序列中。 算法可用递归或递推实现，从相邻的两两元素开始不断调用上面的核心操作组成较长有序序列直到完成整个序列。 算法进行一趟归并就得到一个局部有序的完整新序列，n个元素共需要log2n趟归并，每趟完成比较操作n次（1次得到序列的1个值），得到的新序列写到结果序列空间中，下一趟之前要先将结果序列复制一份到临时空间，下一趟归并在临时空间上进行。因此时间复杂度nlog2n，空间上除了原始序列空间n、结果序列空间n，还需要辅助临时空间n。 接下来看外部排序。外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行多路归并排序。 多路归并排序算法在常见数据结构书中都有涉及。从2路到多路（k路），增大k可以减少外存信息读写时间，但k个归并段中选取最小的记录需要比较k-1次，为得到u个记录的一个有序段共需要(u-1)(k-1)次，若归并趟数为s次，那么对n个记录的文件进行外排时，内部归并过程中进行的总的比较次数为s(n-1)(k-1)，也即(向上取整)(logkm)(k-1)(n-1)=(向上取整)(log2m/log2k)(k-1)(n-1)，而(k-1)/log2k随k增而增因此内部归并时间随k增长而增长了，抵消了外存读写减少的时间，这样做不行，由此引出了“败者树”tree of loser的使用。在内部归并过程中利用败者树将k个归并段中选取最小记录比较的次数降为(向上取整)(log2k)次使总比较次数为(向上取整)(log2m)(n-1)，与k无关。 败者树是完全二叉树，因此数据结构可以采用一维数组。其元素个数为k个叶子结点、k-1个比较结点、1个冠军结点共2k个。ls[0]为冠军结点，ls[1]--ls[k-1]为比较结点，ls[k]--ls[2k-1]为叶子结点（同时用另外一个指针索引b[0]--b[k-1]指向）。另外bk为一个附加的辅助空间，不属于败者树，初始化时存着MINKEY的值。 多路归并排序算法的过程大致为：首先将k个归并段中的首元素关键字依次存入

实验四排序实验报告

数据结构实验报告 实验名称：实验四排序 学生姓名： 班级： 班内序号： 学号： 日期：2012年12月21日 1、实验要求 题目2 使用链表实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据。 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）。 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。

编写测试main()函数测试线性表的正确性。2、程序分析 2.1存储结构 说明：本程序排序序列的存储由链表来完成。 其存储结构如下图所示。 (1)单链表存储结构： （2）结点结构 struct Node {

int data; Node * next; }; 示意图： 2.2关键算法分析 一：关键算法 (一)直接插入排序void LinkSort::InsertSort() 直接插入排序是插入排序中最简单的排序方法，其基本思想是：依次将待排序序列中的每一个记录插入到一个已排好的序列中，直到全部记录都排好序。 （1）算法自然语言 1.将整个待排序的记录序列划分成有序区和无序区，初始时有序区为待排序记录序列中的第一个记录，无序区包括所有剩余待排序的记录； 2.将无须去的第一个记录插入到有序区的合适位置中，从而使无序区减少一个记录，有序区增加一个记录； 3.重复执行2，直到无序区中没有记录为止。 （2）源代码 void LinkSort::InsertSort() //从第二个元素开始，寻找前面那个比它大的

归并排序算法的基本思想及算法实现示例

归并排序算法的基本思想及算法实现示例 归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。 两路归并算法 1、算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。 （1）合并过程 合并过程中，设置i，j和p三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1[p]中，然后将被复制记录的指针i或j加1，以及指向复制位置的指针p加1。 重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子文件中剩余记录依次复制到R1中即可。 （2）动态申请R1 实现时，R1是动态申请的，因为申请的空间可能很大，故须加入申请空间是否成功的处理。 2、归并算法 void Merge(SeqList R，int low，int m，int high) {//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的 //子文件R[low..high] int i=low，j=m+1，p=0；//置初始值 RecType *R1；//R1是局部向量，若p定义为此类型指针速度更快 R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))； if(! R1) //申请空间失败 Error("Insufficient memory available!")； while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上 R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]； while(i<=m) //若第1个子文件非空，则复制剩余记录到R1中 R1[p++]=R[i++]； while(j<=high) //若第2个子文件非空，则复制剩余记录到R1中 R1[p++]=R[j++]； for(p=0，i=low；i<=high；p++，i++) R=R1[p]；//归并完成后将结果复制回R[low..high] } //Merge 归并排序 归并排序有两种实现方法：自底向上和自顶向下。

归并排序实验报告

篇一：归并排序与快速排序实验报告 一、实验内容： 对二路归并排序和快速排序对于逆序的顺序数的排序时间复杂度比较。 二、所用算法的基本思想及复杂度分析： 1、归并排序 1）基本思想：运用分治法，其分治策略为： ①划分：将待排序列 r1,r2,……,rn划分为两个长度相等的子序列 r1,……,rn/2和rn/2+1,……,rn。 ②求解子问题：分别对这两个子序列进行排序，得到两个有序子序列。 ③合并：将这两个有序子序列合并成一个有序子序列。 2）复杂度分析： 二路归并排序的时间代价是o(nlog2n)。二路归并排序在合并过程中需要与原始记录序列同样数量的存储空间，因此其空间复杂性o(n)。 2、快速排序： 1）基本思想：运用分治法，其分治策略为： ①划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列 r1……ri-1和ri+1……rn，轴值的位置i在划分的过程中确定，并且前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值。 ②求解子问题：分别对划分后的每一个子序列递归处理。 ③合并：由于对子序列r1……ri-1和ri+1……rn的排序是就地进行的，所以合并不需要执行任何操作。 2）复杂度分析： 快速排序在平均时间复杂性是o(nlog2n)。最坏的情况下是o(n^2)。 三、源程序及注释： 1、归并排序 #include<iostream> #include<fstream> #include windows.h using namespace std; void merge(int r[],int r1[],int s,int m,int t ) } int mergesort(int r[],int r1[],int s,int t) { } void main() int i=s; int j=m+1; int k=s; while(i<=m&&j<=t) {} if(i<=m)while(i<=m) r1[k++]=r[i++];//第一个没处理完，进行收尾if(r[i]<=r[j])r1[k++]=r[i++];//取r[i]和r[j]中较小的放入r1[k]中else r1[k++]=r[j++]; else while(j<=t) r1[k++]=r[j++];//第二个没处理完，进行收尾for(int l=0;l<k;l++) { } r[l]=r1[l];//将合并完成后的r1[]序列送回r[]中if(s==t)r1[s]=r[s]; else{int m; m=(s+t)/2; mergesort(r,r1,s,m);//归并排序前半个子序列 mergesort(r,r1,m+1,t); //归并排序后半个子序列 merge(r1,r,s,m,t);//合并两个已排序的子序列 }return 0; int a[100000]; int a1[10000];

数据结构之归并排序

算法与数据结构实验报告 实验六 实验名称:归并排序问题 姓名：XXX 学号：xxxxxxxxxx 专业：软件工程 班级：x班 指导教师：xxx 日期: 2013年X月X日

一、实验目的 了解归并排序的排序思想，对于给定的关键字序列进行归并排序输出。二、实验内容与实验步骤 内容：设计二路归并算法。 问题描述如下：输入数据第1行有1整数k，表示需要排序的序列个数。以下k行，每行第一个整数m，表示待排序序列的长度，后面的m个整数表示待排序序列。将k个待排序序列的归并排序结果分k行输出。 步骤： 1将一维数组中前后相邻的两个有序序列归并为一个有序序列； 其算法为：void merge(dataList& L, dataList& L1,int left, int mid, int right){}； 2 对顺序表L作归并排序； 其算法为：void MergePass (dataList& L, dataList& L1, int len){}； 3 将SR[s..t]归并为排序为TR1[s..t]； 其算法为：void MergeSort (dataList& L){}； 4 调试数据，程序结束； 三、实验环境 操作系统winXP、开发平台:Microsoft Visual C++6.0 四、实验过程与分析 归并排序算法大大缩短了排序的时间复杂度，虽然程序代码复杂，但实现的基理相当简单。从运行结果可知，该程序达到了预期效果。 五、实验结论 测试数据：测试结果： 3 7 49 38 65 97 76 13 27 13 27 38 49 65 76 97 10 36 25 48 12 65 25 43 58 76 32 12 25 25 32 36 43 48 58 65 76 6 12 32 49 58 65 79 12 32 49 58 65 79 运行结果：

大文件内容排序,多路归并排序算法

package com.igo.util.file; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.SortedSet; import java.util.TreeSet; import org.slf4j.Logger; /** * * 外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存， * 需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。* 外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装人内存的部分， * 分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。* @author ZhaoWeikai * Company: * 2010-12-23 下午02:25:00 */ public class MergeSort { private static final Logger log = org.slf4j.LoggerFactory.getLogger(MergeSort.class); /** 拆分大小, 单位:行*/ private static int SPLIT_SIZE = 100000; public static void main(String[] args) throws Exception { List list = FileUtil.listFiles("E:\\log\\test"); mergeFile(list, "e:/log/testMergeSort.txt"); } public static boolean mergeSort(List originFileList, String outPutFilePath, String tempPath) throws Exception { https://www.wendangku.net/doc/bf6320137.html,("mergeSort start............................................."); FileUtil.createDir(tempPath); if (originFileList == null || originFileList.size() == 0) {

排序综合实验报告

数据结构 排序算法综合实验报告 姓名：xx x x 班级：10电信1 学号：xxx 指导老师：胡圣荣 日期：2012.12.15～2013.1.5 华南农业大学工程学院

算法基本思想： 1、插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已经排序好的序列中的适当位置，直到全部记录插入完毕为止。 （1）直接插入排序：在排序过程中，每次都讲无序区中第一条记录插入到有序区中适当位置，使其仍保持有序。初始时，取第一条记录为有序区，其他记录为无序区。显然，随着排序过程的进行，有序区不断扩大，无序区不断缩小。最终无序区变为空，有序区中包含了所有的记录，排序结束。 （2）希尔排序：将排序表分成若干组，所有相隔为某个“增量”的记录为一组，在各组内进行直接插入排序；初始时增量d1较大，分组较多（每组的记录数少），以后增量逐渐减少，分组减少（每组的记录数增多），直到最后增量为1（d1>d2>...>dt=1）,所有记录放为一组，再整体进行一次直接插入排序。 2、交换排序：每次比较两个待排序的记录，如果发现他们关键字的次序与排序要求相反时就交换两者的位置，直到没有反序的记录为止。 （1）冒泡排序：设想排序表R[1]到R[n]垂直放置，将每个记录R[i]看作是重量为R[i].key 的气泡；根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。 （2）快速排序：在待排序的n个记录中任取一个作为“基准”，将其与记录分为两组，第一组中个记录的键值均小于或等于基准的键值，第二组中个记录的键值均大于或等于基准的键值，而基准就排在这两组中间（这也是该记录的最终位置），这称为一趟快速排序（或一次划分）。对所分成的两组重复上述方法，直到所有记录都排在适当位置为止。 3、选择排序：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已排好序的子序列的后面（或最前），直到全部记录排序完毕。 （1）直接选择排序：首先，所有记录组成初始无序区R[1]到R[n]，从中选出键值最小的记录，与无序区第一个记录R[1]交换；新的无序区为R[2]到R[n]，从中再选出键值最小的记录，与无序区第一个记录R[2]交换；类似，第i趟排序时R[1]到R[i-1]是有序区，无序区为R[i]到R[n]，从中选出键值最小的记录，将它与无序区第一个记录R[i]交换，R[1]到R[i]变为新的有序区。因为每趟排序都使有序区中增加一个记录，所以，进行n-1趟排序后，整个排序表就全部有序了。 （2）堆排序：利用小根堆（或大根堆）来选取当前无序区中关键字最小（或最大）的记录来实现排序的。下面介绍利用大根堆来排序。首先，将初始无序区调整为一个大根堆，输出关键字最大的堆顶记录后，将剩下的n-1个记录在重建为堆，于是便得到次小值。如此反复执行，知道全部元素输出完，从而得到一个有序序列。 4、并归排序：指将若干个已排序的子表合成一个有序表。 （1）二路并归排序：开始时，将排序表R[1]到R[n]看成n个长度为1的有序子表，把这些子表两两并归，便得到n/2个有序的子表（当n为奇数时，并归后仍是有一个长度为1的子表）；然后，再把这n/2个有序的子表两两并归，如此反复，直到最后得到一个程度为n的有序表为止。