分治算法实验(用分治法实现归并排序算法)

排序算法比较实验报告

信息学部算法分析 上机报告 学号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

C (++)内部排序汇总(快速排序&冒泡排序&堆排序&选择排序&插入排序&归并排序)

#include #include #include #include #define M 30001 random(int a[30001]) { int i; for(i=1;i<30001;i++) a[i]=rand()%30001; }//随机生成30000个数函数 int change1(char a[81]) { int b=0,n,i; for(i=0;a[i]!=0;i++); n=i-1; for(;i>1;i--) b+=((int)pow(10,n+1-i))*(a[i-1]-48); if(a[0]=='-') b=b*(-1); else b+=((int)pow(10,n))*(a[0]-48); return b; }//字符转化成整型 insort(int a[30001]) { int i,j,temp,temp1,n; int count=0; n=30001; for(i=1;i=0;j--)/* 每次循环完毕数组的0到i-1项为一个有序的序列*/ { count=0;/*这里count是标记位，可以减少比较次数*/ if(a[j]>temp) { temp1=a[j+1]; a[j+1]=a[j]; a[j]=temp1;

count++; }//满足条件，前移 if(count==0) break;//位置恰当，退出 } } }//insort插入排序函数 selsort(int a[30001]) { int i,j,temp; for(i=1;i<30000;i++) for(j=i+1;j<30001;j++) if(a[i]>a[j]) { temp=a[j]; a[j]=a[i]; a[i]=temp; } }//选择排序 bubsort(int a[30001]) { int i,j,temp; for(i=1;i<30001;i++) for(j=30000;j>i;j--) { if(a[j-1]>a[j]) { temp=a[j-1]; a[j-1]=a[j]; a[j]=temp; } } }//冒泡排序 int partition(int a[30001],int low,int high)

算法排序问题实验报告

《排序问题求解》实验报告 一、算法的基本思想 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=privotkey do high←high-1 A[low]←A[high] //将比枢轴记录小的记录移到低端 while low

简单的归并排序算法例子

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

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

归并排序算法实现（迭代和递归）\递归实现归并排序的原理如下： 递归分割: 递归到达底部后排序返回: 最终实现排序： #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

分治算法实验(用分治法实现快速排序算法)

算法分析与设计实验报告第四次附加实验

while (a[--j]>x); if (i>=j) { break; } Swap(a[i],a[j]); } a[p] = a[j]; //将基准元素放在合适的位置 a[j] = x; return j; } //通过RandomizedPartition函数来产生随机的划分 template vclass Type> int RandomizedPartition(Type a[], int p, int r) { int i = Random(p,r); Swap(a[i],a[p]); return Partition(a,p,r); } 较小个数排序序列的结果: 测试结果 较大个数排序序列的结果:

实验心得 快速排序在之前的数据结构中也是学过的，在几大排序算法中，快速排序和归并排序尤其是 重中之重，之前的快速排序都是给定确定的轴值，所以存在一些极端的情况使得时间复杂度 很高，排序的效果并不是很好，现在学习的一种利用随机化的快速排序算法，通过随机的确 定轴值，从而可以期望划分是较对称 的，减少了出现极端情况的次数，使得排序的效率挺高了很多， 化算法想呼应，而且关键的是对于随机生成函数，通过这一次的 学习终于弄明白是怎么回事了，不错。 与后面的随机实 验和自己的 实验得分助教签名 附录： 完整代码(分治法) //随机后标记元素后的快速排序 #i nclude #in elude #inelude #include using namespacestd; template < class Type> void S &x,Type &y); // 声明swap函数 inline int Random(int x, int y); // 声明内联函数 template < class Type> int Partition(Type a[], int p, int r); // 声明 Partition 函数template int RandomizedPartition(Type a[], int p, int r); // 声明 RandomizedPartition 函数 int a[1000000]; //定义全局变量用来存放要查找的数组 更大个数排序序列的结果:

各种排序实验报告

【一】需求分析 课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。 为了运行时的方便，将八种排序方法进行编号，其中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<<"排序之后的数组为："<

分治法实现快速排序与两路合并排序

实验报告 （2015 / 2016 学年第二学期） 课程名称 实验名称分治法实现快速排序与两路合并排序 实验时间年月日指导单位计算机学院计算机科学与技术系 指导教师 学生姓名班级学号 学院(系) 专业 实验报告

三、实验原理及内容 实验原理： 分治法：即分而治之。将问题分解为规模较小，相互独立，类型相同的问题进行求解。对于无序数组的有序排序也就是按某种方式将序列分成两个或多个子序列，分别进行排序，再将已排序的子序列合并成一个有序序列。 实验内容： 两路合并排序算法的基本思想是：将待排序元素序列一分为二，得到两个长度基本相等的子序列，其过程类似于对半搜索；然后将子序列分别排序，如果子序列较长，还可以继续细分，知道子序列长度不超过1为止。 以上的实现由下列代码执行： void SortableList::MergeSort() { MergeSort(0,n-1); } void SortableList::MergeSort(int left,int right) { if (left

归并排序分治策略的设计与实现

实验名称归并排序分治策略的设计与实现实验方案实验成绩实验日期实验室信息系统设计与仿真室I 实验操作 实验台号班级姓名实验结果 一、实验目的 1、熟悉分治法求解问题的抽象控制策略； 2、熟悉在顺序存储表示下求解分类问题的递归算法设计； 3、通过实例转换, 掌握分治法应用。 二、实验任务 ①从文件中读取数据信息； ②利用归并排序算法，进行排序； ③输出排序结果。 三、实验设计方案 1、结构体设计 用数组存放排序数据。 2、自定义函数设计 ①函数原型声明 int input(int A[]); //从文件读入待排序的数据 void merge(int A[],int low,int mid,int high); // 两个相邻有序数组的归并 void mergesort(int A[],int low,int high); // 归并排序 void input(int A[], int n); // 输出排序结果 ②两个相邻的有序子数组的合并 思路：从两个已排好序的子数组的首元素开始，依次比较大小，按从小到大的顺序存放在b[]数组中，然后转存到A[]数组中。 void merge(int A[],int low,int mid,int high) { int b[N]; int i,j,k = 0; int l = low; //已排序部分1的起始下标 int h = mid+1; //已排序部分2的起始下标 while(l <= mid && h <= high) //两个有序部分合并到b数组中 if(A[l] < A[h]) b[k++] = A[l++]; else

分治法实现快速排序

实验一 实验名称：利用分治法实现快速排序 实验时 2012 年12月成绩： 间： 一、实验目的 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。 本实验的目的是利用分治策略实现快速排序算法。 二、实验内容 快速排序算法是基于分治策略的排序算法。其基本思想是，对于输入的子数组a[p:r],按以下三个步骤进行排序。 （1）分解:以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q] 和a[q+1:r]， 使a[p:q-1]中任何一个元素小于等于a[q]，而a[q+1:r]中任何一个元素大于等于 a[q]。下标q在划分过程中确定。 （2）递归求解：通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序。 （3）合并：由于对a[p:q-1]和a[q+1:r]的排序是就地进行的，所以在a[p:q-1] 和a[q+1:r]都已排好的序后，不需要执行任何计算，a[p:r]就已排好序。 基于这个思想，可实现的快速排序算法如下： void QuickSort(i nt a[],i nt p,i nt r) if(p

int q=Partition(a,p,r); QuickSort(a,p,q-1); QuickSort(a,q+1,r); } } 对含有n 个元素的数组a[0;n-1] 进行快速排序只要调用QuickSort(a,0,n-1) 即可。 上述算法中的函数Partition ，以确定的一个基准元素a[p] 对子数组a[p:r] 进行划分，它是快速排序算法的关键。 int Partition(int a[],int p,int r) { int i=p,j=r+1; int x=a[p]; while(true) { while(a[++i]x); if(i>=j) break; Swap(a[i],a[j]); } a[p]=a[j];

排序算法实验报告

实验课程：算法分析与设计 实验名称：几种排序算法的平均性能比较（验证型实验） 实验目标： （1）几种排序算法在平均情况下哪一个更快。 （2）加深对时间复杂度概念的理解。 实验任务： （1）实现几种排序算法（selectionsort, insertionsort,bottomupsort,quicksort, 堆排序）。对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A((low+high)/2)中其值居中者。（2）随机产生20组数据（比如n=5000i，1≤i≤20）。数据均属于范围（0，105）内的整数。对于同一组数据，运行以上几种排序算法，并记录各自的运行时间（以毫秒为单位）。（3）根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数，并得出结论。 实验设备及环境： PC；C/C++等编程语言。 实验主要步骤： (1)明确实验目标和具体任务； (2)理解实验所涉及的几个分类算法； (3)编写程序实现上述分类算法； (4)设计实验数据并运行程序、记录运行的结果； (5)根据实验数据及其结果得出结论； (6)实验后的心得体会。 一:问题分析（包括问题描述、建模、算法的基本思想及程序实现的技巧等）：1:随机生成n个0到100000的随机数用来排序的算法如下. for(int n=1000;n<20000;n+=1000) { int a[]=new int[n]; for(int i=0;i

分治算法实验(用分治法实现归并排序算法)

算法分析与设计实验报告第二次实验

对于归并排序，在之前的数据结构已经学过了，本来以为代码实现起来会比较

附录： 完整代码（分治法） #include #include #include using namespace std; void merge(int A[],int B[],int low,int mid,int high) //将两个子序列合并，排序成一个有序的序列 { int i=low; int j=mid+1; int k=low; while((i<=mid)&&(j<=high)) //两两比较，将较小的数放在临时的数组中{ if(A[i]<=A[j]) { B[k++]=A[i++]; } else { B[k++]=A[j++]; } } if(i>mid) //如果最后左半边子序列已经全部排完，就将右边子序列剩下的元素直接复制到临时的数组中 { for(int last=j;last<=high;last++) { B[k++]=A[last]; } } else//如果最后右半边子序列已经全部排完，就将左边子序列剩下的元素直接复制到临时的数组中

{ for(int last=i;last<=mid;last++) { B[k++]=A[last]; } } } void mergesort(int a[],int b[],int left,int right) //分治法实现归并排序，利用递归实现{ if(left>n; ran(a,n); //生成数组

算法分析实验报告--分治策略

分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX

一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让

这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include #include<> #define MAX 10 using namespace std; void merge(int array[],int p,int q,int r) { int i,k; int begin1,end1,begin2,end2; int* temp = new int[r-p+1]; begin1 = p; end1 = q; begin2 = q+1; end2 = r; k = 0; while((begin1 <= end1)&&(begin2 <= end2)) { if(array[begin1] < array[begin2]) { temp[k] = array[begin1]; begin1++; } else { temp[k] = array[begin2]; begin2++; } k++; } while(begin1 <= end1) { temp[k++] = array[begin1++]; }

数据结构(C语言版)实验报告-(内部排序算法比较)

数据结构与算法》实验报告 一、需求分析 问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 基本要求： （l ）对以下 6 种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 （2 ）待排序表的表长不小于100000 ；其中的数据要用伪随机数程序产生；至少要用 5 组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为 3 次移动）。 （ 3 ）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。数据测试：二．概要设计 1. 程序所需的抽象数据类型的定义： typedef int BOOL; typedef struct StudentData { } Data; typedef struct LinkList { Data Record[MAXSIZE]; int num; // 存放关键字 int Length; // 数组长度// 用数组存放所有的随机数 // 说明BOOL 是int 的别名 } LinkList int RandArray[MAXSIZE]; // 定义长度为MAXSIZE 的随机数组 void RandomNum() // 随机生成函数

void InitLinkList(LinkList* L) // 初始化链表 // 比较所有排序 2 . 各程序模块之间的层次（调用）关系： BOOL LT(int i, int j,int* CmpNum) // 比较 i 和 j 的大小 void Display(LinkList* L) // 显示输出函数 void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum) void QuickSort (LinkList* L, // 快速排序 void HeapSort (LinkList* L, // 堆排序 void BubbleSort(LinkList* L, // 冒泡排序 void SelSort(LinkList* L, // 选择排序 int* CmpNum, int* ChgNum) int* CmpNum, int* ChgNum) int* CmpNum, int* ChgNum) * CmpNum, int* ChgNum) void Compare(LinkList* L,int* CmpNum, int* ChgNum) // 希尔排序

分治法实现快速排序

实验一 实验名称：利用分治法实现快速排序实验时间: 2012年12月成绩：一、实验目的 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。 本实验的目的是利用分治策略实现快速排序算法。 二、实验内容 快速排序算法是基于分治策略的排序算法。其基本思想是，对于输入的子数组a[p:r],按以下三个步骤进行排序。 （1）分解：以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q]和a[q+1:r]，使a[p:q-1]中任何一个元素小于等于a[q]，而a[q+1:r]中任何一个元素大于等于a[q]。下标q在划分过程中确定。 （2）递归求解：通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序。 （3）合并：由于对a[p:q-1]和a[q+1:r]的排序是就地进行的，所以在a[p:q-1]和a[q+1:r]都已排好的序后，不需要执行任何计算，a[p:r]就已排好序。基于这个思想，可实现的快速排序算法如下：void QuickSort(int a[],int p,int r)

{ if(px); if(i>=j) break;

快速排序实验报告

南京邮电大学通达学院 实验报告 实验名称：快速排序算法 课程名称：微型计算机原理与接口技术 姓名班级学号：钱煜中 142501 14250120 实验时间：2016.12.2

快速排序原理 一、实验原理： 快速排序算法quick sort主要是利用分治递归的思想进行排序的方法。它的原理是首先从待排序的原始序列a[p,…,r]中选取一个元素a[q]作为分界点（pivot），然后将序列分为两个子序列，左边子序列a[p,…,q-1]元素的值都小于分界点m，右边子序列a[q+1,…,r]元素值都大于分界点的值，此时得到的序列命名为a’，而a[q]应该处于其排好序后的正确位置。然后利用递归的思想，对左右两个子序列a[p,…,q-1]和a[q+1,…,r]再分别进行排序，直到子序列的长度为1结束，序列有序。 其中，选取a中的基准分界点的方式有多种，或者选择序列的首元素a[p]，或者选择序列的尾元素a[r]，或者选择序列中间位置的元素a[(p+r)/2]，或者取这三个元素按照大小排序后的中间值。 例子： a = [38, 81, 22,48,13,69, 93, 14, 45, 58, 79, 72]，取[(left+right)/2]处的元素作为分界点（pivot）的值。具体第一次分区过程如下：

因此，第一次分区，以69为分界点，结果为: a’= [14, 58, 22, 48, 13, 38, 45, 69, 93, 81, 79, 72]。 二、实验代码 #include int fast_sort(int *a,int i,int j,int *p,int **b) { int k,temp,f,g; g=*p; g=(12*g)-12; //intf("成功进入快速排序 g=%d\n",g); k=i; i++;

数据结构实验-归并排序算法

大连理工大学实验预习报告 学院（系）：电信专业：班级： 姓名：学号：组：___ 实验时间：实验室：实验台： 指导教师签字：成绩： 实验名称Merge sort 一、实验目的和要求 (一)、实验目的 Design the merge sort algorithm and implement it in C language 设计归并排序算法并于C语言实现。 (二)、实验要求 Requirements: 1) Analyze the time complexity of your algorithm 2) Submit the document explaining your algorithm as well as the source code. 要求： 1)分析算法的时间复杂度。 2) 提交的文档中说明你的算法和源代码。 二、实验原理 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可 解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？ 可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

算法分析与复杂性理论 实验报告 基本排序

深圳大学实验报告 课程名称：算法设计与分析 实验名称：多种排序算法的算法实现及性能比较 学院：计算机与软件学院专业：计算机科学与技术报告人：张健哲学号：2013150372 班级： 3 同组人：无 指导教师：李炎然 实验时间：2015/3/25——2015/4/8 实验报告提交时间：2015/4/8 教务处制

一．实验目的 1.掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理 2.掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。二．实验步骤与结果 实验总体思路： 利用switch结构来选择实验所要用的排序算法，每一种排序都用相同的计算运行时间的代码，不同的算法就在算法实现部分进行改动（如下代码1至5所示）。不断的改变数据规模，每一个规模在实验时，用循环进行多次实验并作为样本记录消耗的时间。最后输出在不同排序算法下，不同的数据规模的20次实验样本和平均用时（如下图1至5所示）。 各排序算法的实现及实验结果： （注1：以下代码全部为伪代码，具体代码实现请参照程序中的代码） （注2：图中显示的时间单位均为毫秒，图中“排序所花时间”一项为平均消耗时间，平均消耗时间结果以20组样本计算平均值后取整得到（并非四舍五入）。） 1、选择排序 代码1： for i=0 to n-2 min=i for j= i+1 to n-1 if ele[min]>ele[j] min=j swap(ele[i],ele[min]) //交换 图1、选择排序在不同数据规模下排序所消耗的时间

2、冒泡排序 代码2： for i= 0 to n-1 for j=0 to n-1-i if a[j]>a[j+1] swap(a[j],a[j+1]) //交换 图2、冒泡排序在不同数据规模下排序所消耗的时间 3、合并排序 代码3： Merge(ele[1...n],left,right) middle=(left+right)/2 if right>1eft+1 Merge(ele,left,middle) Merge(ele,middle+1,right) l←left r←right i←left while l<=middle&&r<=right //两组分别一一比较，数据小的放入ele if ele[l]<=ele[r] t[i++]←ele[l++] else t[i++]←ele[r++] while l>middle&&r<=r //只剩一组还有剩余的时，将剩下的按顺序放入ele[i++]=s[r++] while l<=middle && r>right ele[i++]=s[l++];