下载文档原格式
如何应用分治算法求解问题分治算法，英文名为Divide and Conquer Algorithm，是一种高效的算法设计策略，在计算机科学中有着广泛的应用。
该算法将一个大问题分解成多个小问题，各自独立地解决，再将结果合并起来得到最终结果。
在本文中，我们将阐述如何应用分治算法求解问题，并通过几个实例来具体说明该算法的应用。
一、分治算法的原理分治算法的核心思想是将一个大问题分解成若干个小问题来解决，然后将这些小问题的解组合起来生成大问题的解。
其具体步骤如下：1. 分解：将原问题划分成若干个规模较小的子问题。
2. 解决：递归地解决每个子问题。
如果子问题足够小，则直接求解。
3. 合并：将所有子问题的解合并成原问题的解。
分治算法的主要优点在于它可以有效地缩小问题规模，从而缩短整个算法的执行时间。
另外，该算法天然适用于并行计算，因为每个子问题都是独立求解的。
二、分治算法的应用分治算法在各种领域都有广泛应用，包括数学、自然科学、计算机科学等。
以计算机科学领域为例，分治算法常常用于解决以下类型的问题：1. 排序问题2. 查找问题3. 字符串匹配问题4. 最大子序列和问题5. 矩阵乘法问题6. 图形问题下面我们将一一讲解这些问题的分治算法实现。
1. 排序问题排序问题是在一组数据中将其按指定规律进行排列的问题。
在计算机科学中，排序算法是十分重要的一类算法。
其中，分治算法由于其高效性和可并行性被广泛应用。
常用的分治排序算法包括归并排序和快速排序。
归并排序的基本思想是将待排序元素以中心点为界分成两个序列，对每个序列进行排序，然后将两个序列合并成一个有序序列；而快速排序则利用了分割的思想，通过每次选取一个元素作为“轴点”，将数组分成小于轴点和大于轴点的两部分，对这两部分分别进行快速排序。
2. 查找问题查找问题是在一组数据中寻找某个元素的问题。
分治算法在查找问题中的应用主要体现在二分查找中。
在二分查找中，我们首先将已排序的数组分成两半，在其中一半中查找目标值。
《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？2.算法分析的目的是什么？3.算法的时间复杂性与问题的什么因素相关？4.算法的渐进时间复杂性的含义？5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？6.简述二分检索（折半查找）算法的基本过程。
7.背包问题的目标函数和贪心算法最优化量度相同吗？8.采用回溯法求解的问题，其解如何表示？有什么规定？9.回溯法的搜索特点是什么？10.n皇后问题回溯算法的判别函数place的基本流程是什么？11.为什么用分治法设计的算法一般有递归调用？12.为什么要分析最坏情况下的算法时间复杂性？13.简述渐进时间复杂性上界的定义。
14.二分检索算法最多的比较次数？15.快速排序算法最坏情况下需要多少次比较运算？16.贪心算法的基本思想？17.回溯法的解（x1,x2,……x n）的隐约束一般指什么？18.阐述归并排序的分治思路。
19.快速排序的基本思想是什么。
20.什么是直接递归和间接递归？消除递归一般要用到什么数据结构？21.什么是哈密顿环问题？22.用回溯法求解哈密顿环，如何定义判定函数？23.请写出prim算法的基本思想。
二、复杂性分析1、MERGESORT(low，high)if low<high；then mid←(low，high)/2；MERGESORT(low，mid)；MERGESORT(mid+1，high)；MERGE(low，mid，high)；endifend MERGESORT2、procedure S1(P，W，M，X，n)i←1; a←0while i≤ n doif W(i)>M then return endifa←a+ii←i+1 ;repeatend3.procedure PARTITION(m,p)Integer m,p,i;global A(m:p-1)v←A(m);i←mlooploop i←i+1 until A(i) ≥v repeatloop p←p-1 until A(p) ≤v repeatif i<pthen call INTERCHANGE(A(i),A(p))else exitendifrepeatA(m) ←A(p);A(p) ←vEnd PARTITION4.procedure F1(n)if n<2 then return(1)else return(F2(2,n,1,1))endifend F1procedure F2(i,n,x,y)if i≤nthen call F2(i+1,n,y,x+y)endifreturn(y)end F25.procedure MAX(A,n,j)xmax←A(1);j←1for i←2 to n doif A(i)>xmax then xmax←A(i); j←i;endif repeatend MAX6.procedure BINSRCH(A,n,x,j)integer low,high,mid,j,n;low←1;high←nwhile low≤high domid←|_(low+high)/2_|case:x<A(mid):high←mid-1:x>A(mid):low←mid+1:else:j ←mid; returnendcase repeat j ←0 end BINSRCH三、算法理解1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。
第1篇一、实验目的通过本次实验，掌握常见算法的设计原理、实现方法以及性能分析。
通过实际编程，加深对算法的理解，提高编程能力，并学会运用算法解决实际问题。
二、实验内容本次实验选择了以下常见算法进行设计和实现：1. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。
2. 查找算法：顺序查找、二分查找。
3. 图算法：深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）。
4. 动态规划算法：0-1背包问题。
三、实验原理1. 排序算法：排序算法的主要目的是将一组数据按照一定的顺序排列。
常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。
2. 查找算法：查找算法用于在数据集中查找特定的元素。
常见的查找算法包括顺序查找和二分查找。
3. 图算法：图算法用于处理图结构的数据。
常见的图算法包括深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）等。
4. 动态规划算法：动态规划算法是一种将复杂问题分解为子问题，通过求解子问题来求解原问题的算法。
常见的动态规划算法包括0-1背包问题。
四、实验过程1. 排序算法（1）冒泡排序：通过比较相邻元素，如果顺序错误则交换，重复此过程，直到没有需要交换的元素。
（2）选择排序：每次从剩余元素中选取最小（或最大）的元素，放到已排序序列的末尾。
（3）插入排序：将未排序的数据插入到已排序序列中适当的位置。
（4）快速排序：选择一个枢纽元素，将序列分为两部分，使左侧不大于枢纽，右侧不小于枢纽，然后递归地对两部分进行快速排序。
（5）归并排序：将序列分为两半，分别对两半进行归并排序，然后将排序好的两半合并。
（6）堆排序：将序列构建成最大堆，然后重复取出堆顶元素，并调整剩余元素，使剩余元素仍满足最大堆的性质。
2. 查找算法（1）顺序查找：从序列的第一个元素开始，依次比较，直到找到目标元素或遍历完整个序列。
二叉树的快速排序、归并排序方法一、快速排序快速排序采用的是分治法策略，其基本思路是先选定一个基准数（一般取第一个元素），将待排序序列抽象成两个子序列：小于基准数的子序列和大于等于基准数的子序列，然后递归地对这两个子序列排序。
1. 递归实现（1）选定基准数题目要求采用第一个元素作为基准数，因此可以直接将其取出。
（2）划分序列接下来需要将待排序序列划分成两个子序列。
我们定义两个指针 i 和 j，从待排序序列的第二个元素和最后一个元素位置开始，分别向左和向右扫描，直到 i 和 j 相遇为止。
在扫描过程中，将小于等于基准数的元素移到左边（即与左侧序列交换），将大于基准数的元素移到右边（即与右侧序列交换）。
当 i=j 时，扫描结束。
（3）递归排序子序列完成划分后，左右两个子序列就确定了下来。
接下来分别对左右两个子序列递归调用快速排序算法即可。
2. 非递归实现上述方法是快速排序的递归实现。
对于大量数据或深度递归的情况，可能会出现栈溢出等问题，因此还可以使用非递归实现。
非递归实现采用的是栈结构，将待排序序列分成若干子序列后，依次将其入栈并标注其位置信息，然后将栈中元素依次出栈并分割、排序，直至栈为空。
二、归并排序归并排序同样采用的是分治思想。
其基本思路是将待排序序列拆分成若干个子序列，直至每个子序列只有一个元素，然后将相邻的子序列两两合并，直至合并成一个有序序列。
1. 递归实现（1）拆分子序列归并排序先将待排序序列进行拆分，具体方法是将序列平分成两个子序列，然后递归地对子序列进行拆分直至每个子序列只剩下一个元素。
（2）合并有序子序列在完成子序列的拆分后，接下来需要将相邻的子序列两两合并为一个有序序列。
我们先定义三个指针 i、j 和 k，分别指向待合并的左侧子序列、右侧子序列和合并后的序列。
在进行合并时，从两个子序列的起始位置开始比较，将两个子序列中较小的元素移动到合并后的序列中。
具体操作如下：- 当左侧子序列的第一个元素小于等于右侧子序列的第一个元素时，将左侧子序列的第一个元素移动到合并后的序列中，并将指针 i 和 k 分别加 1。
总结分治法的基本思想分治法是一种非常重要的算法设计的思想和方法。
它的基本思想是将一个大问题划分成若干个相互独立的子问题，然后分别解决这些子问题，最后将子问题的解合并起来得到原问题的解。
在该过程中，分治法可递归地将原问题划分成更小规模的子问题，直到问题的规模足够小，可以将其直接解决。
分治法的基本步骤包括：分解、解决和合并。
首先，分解过程将原问题划分成若干个规模较小且相互独立的子问题。
这一步骤通常通过递归的方式实现。
通过递归，可以将原问题不断地分解成规模更小、更为简单的子问题。
分解得到的子问题可以独立地解决，这是分治法的关键之一。
其次，解决过程将规模较小的子问题逐一求解。
对于子问题的求解可以采用相同的分治法策略，即递归地继续分解成更小的子问题，直到问题足够简单被直接求解。
在这一步骤中，每个子问题的解是相互独立的，可以并行地被求解。
这也是分治法的另一个优势，可以提高问题求解的效率。
最后，合并过程将子问题的解合并成原问题的解。
合并操作将独立求解出来的子问题的解融合在一起，得到原始问题的解。
在这一步骤中，分治法通常会利用子问题的解法，将其组合起来得到原问题的解。
这一步骤是分治法求解问题的最后一步，也是最重要的一步。
通过上述三个步骤，分治法能够有效地解决问题。
它的核心思想是通过逐步分解问题，将原问题转化成更小、更为简单的子问题，然后依次求解子问题，最后将子问题的解合并起来得到原问题的解。
分治法的思想具有普适性和可拓展性，可以应用于各种类型的问题求解。
分治法广泛应用于算法设计和问题求解中。
例如，在排序算法中，归并排序和快速排序都是基于分治法的思想。
归并排序将一个无序的序列划分成两个规模相等的子序列，然后分别对子序列进行排序，最后将两个有序的子序列合并得到一个有序的序列。
快速排序则通过选取一个主元素将序列分为两个部分，然后递归地对两个子序列进行排序。
除了排序问题，分治法还可以应用于图的搜索、最优化问题、数值计算等领域。
算法导论答案第一章：算法概述啊算法的定义算法是一系列解决问题的明确指令。
它是一个有穷步骤集，其中每个步骤或操作由确定性和可行性特征。
算法是通过将预期的输入转换为输出来解决问题的工具。
第二章：插入排序插入排序的思想插入排序是一种简单直观的排序算法，其基本思想是将待排序的序列分为已排序和未排序两部分，每次从未排序的部分中取出一个元素，并将其插入到已排序部分的正确位置，直到所有元素都被排序。
插入排序的算法实现以下是插入排序的伪代码：INSERTION-SORT(A)for j = 2 to A.lengthkey = A[j]// Insert A[j] into the sorted sequence A[1.. j-1].i = j - 1while i > 0 and A[i] > keyA[i + 1] = A[i]i = i - 1A[i + 1] = key插入排序的时间复杂度插入排序的时间复杂度为O(n^2)，其中n是排序的元素个数。
虽然插入排序的最坏情况下的复杂度很高，但是对于小规模的数据集，插入排序是一种较快的排序算法。
第三章：分治策略分治策略的基本思想分治策略是一种解决问题的思想，它将问题的规模不断缩小，直到问题足够小而可以直接解决。
然后将子问题的解合并起来，得到原问题的解。
分治策略的应用实例一种经典的应用分治策略的算法是归并排序。
归并排序将待排序的序列划分为两个子序列，分别排序后再将两个有序子序列合并为一个有序序列。
以下是归并排序的伪代码：MERGE-SORT(A, p, r)if p < rq = floor((p + r) / 2)MERGE-SORT(A, p, q)MERGE-SORT(A, q + 1, r)MERGE(A, p, q, r)MERGE(A, p, q, r)n1 = q - p + 1n2 = r - qlet L[1..n1+1] and R[1..n2+1] be new arraysfor i = 1 to n1L[i] = A[p + i - 1]for j = 1 to n2R[j] = A[q + j]L[n1 + 1] = infinityR[n2 + 1] = infinityi = 1j = 1for k = p to rif L[i] <= R[j]A[k] = L[i]i = i + 1elseA[k] = R[j]j = j + 1分治策略的时间复杂度归并排序的时间复杂度为O(nlogn)，其中n是待排序序列的长度。
一、算法设计实例1、快速排序（分治法）int partition(float a[],int p,int r) {int i=p,j=r+1;float x=a[p];while(1){while(a[++i]<x);while(a[--j]<x);if(i>=j)break;swap(a[i],a[j]);}a[p]=a[j];a[j]=x;return j;}void Quicksort(float a[],int p,int r){//快速排序if(p<r){int q=partition(a,p,r);Quicksort(a,p,q-1);Quicksort(a,p+1,r);}}2、归并排序（分治法）void mergesort(Type a[],int left,int right) {if(left<rigth){int mid=(left+right)/2;//取中点mergesort(a,left,mid);mergesort(a,mid+1,right);mergesort(a,b,left,right);//合并到数组bmergesort(a,b,left,right);//复制到数组a}}3、背包问题（贪心算法）void knapsack(int n,float m,float v[],float w[],float x[]) {sort(n,v,w)//非递增排序int i;for(i=1;i<=n;i++)x[i]=0;float c=m;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}4、活动安排问题（贪心算法）void Greadyselector(int n,Type s[],Type f[],bool A[]) {//s[i]为活动结束时间，f[j]为j活动开始时间A[i]=true;int j=1;for(i=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}5、喷水装置问题（贪心算法）void knansack(int w,int d,float r[],int n){//w为草坪长度d为草坪宽度r[]为喷水装置的喷水半径，//n为n种喷水装置，喷水装置的喷水半径>=d/2sort(r[],n);//降序排序count=0;//记录装置数for(i=1;i<=n;i++)x[i]=0;//初始时，所有喷水装置没有安装x[i]=0for(i=1;w>=0;i++){x[i]=1;count++;w=w-2*sqart(r[i]*r[i]-1);}count<<装置数:<<count<<end1;for(i=1;i<=n;i++)count<<喷水装置半径：<<r[i]<<end1;}6、最优服务问题（贪心算法）double greedy(rector<int>x,int s){rector<int>st(s+1,0);rector<int>su(s+1,0);int n=x.size();//st[]是服务数组，st[j]为第j个队列上的某一个顾客的等待时间//su[]是求和数组，su[j]为第j个队列上所有顾客的等待时间sort(x.begin(),x.end());//每个顾客所需要的服务时间升序排列int i=0,j=0;while(i<n){st[j]+=x[i];//x[i]=x.begin-x.endsu[j]+=st[j];i++;j++;if(j==s)j=0;}double t=0;for(i=0;i<s;i++)t+=su[i];t/=n;return t;}7、石子合并问题（贪心算法）float bebig(int A[],int n) {m=n;sort(A,m);//升序while(m>1){for(i=3;i<=m;i++)if(p<A[i])break;elseA[i-2]=A[i];for(A[i-2]=p;i<=m;i++){A[i-1]=A[i];m--;}}count<<A[1]<<end1}8、石子合并问题（动态规划算法）best[i][j]表示i-j合并化最优值sum[i][j]表示第i个石子到第j个石子的总数量|0f(i,j)=||min{f(i,k)+f(k+1,j)}+sum(i,j)int sum[maxm]int best[maxm][maxn];int n,stme[maxn];int getbest();{//初始化，没有合并for(int i=0;i<n;i++)best[i][j]=0;//还需要进行合并for(int r=1;r<n;r++){for(i=0;i<n-r;i++){int j=i+v;best[i][j]=INT-MAX;int add=sum[j]-(i>0!sum[i-1]:0);//中间断开位置，取最优值for(int k=i;k<j;++k){best[i][j]=min(best[i][j],best[i][k]+best[k+1][j])+add;}}}return best[0][n-1];}9、最小重量机器设计问题（回溯法）typedef struct Qnode{float wei;//重量float val;//价格int ceng;//层次int no;//供应商struct Qnode*Parent;//双亲指针}Qnode;float wei[n+1][m+1]=;float val[n+1][m+1]=;void backstack(Qnode*p){if(p->ceng==n+1){if(bestw>p->wei){testw=p->wei;best=p;}}else{for(i=1;i<=m;i++)k=p->ceng;vt=p->val+val[k][i];wt=p->wei+wei[k][i];if(vt<=d&&wt<=bestw){s=new Qnode;s->val=vt;s->wei=wt;s->ceng=k+1;s->no=1;s->parent=p;backstrack(S);}}}10、最小重量机器设计问题（分支限界法）typedef struct Qnode{float wei;//重量float val;//价格int ceng;//层次int no;//供应商struct Qnode*Parent;//双亲指针}Qnode;float wei[n+1][m+1]=;float val[n+1][m+1]=;void minloading(){float wt=0;float vt=0;float bestw=Max;//最小重量Qnode*best;s=new Qnode;s->wei=0;s->val=0;s->ceng=1;s->no=0;s->parent=null;Iinit_Queue(Q); EnQueue(Q,S);do{p=OutQueue(Q);//出队if(p->ceng==n+1){if(bestw>p->wei){bestw=p->wei;best=p;}}else{for(i=1;i<=m;i++){k=p->ceng;vt=p->val+val[k][i];wt=p->wei+wei[k][i];if(vt<=d&&wt<=bestw){s=new Qnode;s->ceng=k+1;s->wt=wt;s->val=val;s->no=i;s->parent=p;EnQueue(Q,S);}}}}while(!empty(Q));p=best;while(p->parent){count<<部件：<<p->ceng-1<<end1;count<<供应商：<<p->no<<end1;p=p->parent;}}11、快速排序（随机化算法—舍伍德算法）int partion(int a[],int l,int r){key=a[l];int i=l,j=r;while(1){while(a[++i]<key&&i<=r);while(a[--j]>key&&j>=l);if(i>=j)break;if(a[i]!=a[j])swap(a[i],a[j]);}if((j!=l)&&a[l]!=a[j])swap(a[l],a[j]);return j;}int Ranpartion(int a[],int l,int r) {k=rand()%(r-1+l)+1;swap(a[k],a[l]);int ans=partion(a,l,r);return ans;}int Quick_sort(int a[],int l,int r,int k){int p=Randpartion(a,l,r);if(p==k)return a[k];else if(k<p)return Quick_sort(a,l,p-1,k);else{int j=0;for(int i=p+1;i<=r;i++)b[j++]=a[i]return Quick_sort(b,1,j,k-p);}}12、线性选择（随机化算法—舍伍德算法）二、简答题1．分治法的基本思想分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。
《算法设计与分析》教案张静第1章绪论算法理论的两大论题：1. 算法设计2. 算法分析1.1 算法的基本概念1.1.1 为什么要学习算法理由1：算法——程序的灵魂➢问题的求解过程：分析问题→设计算法→编写程序→整理结果➢程序设计研究的四个层次：算法→方法学→语言→工具理由2：提高分析问题的能力算法的形式化→思维的逻辑性、条理性1.1.2 算法及其重要特性算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。
算法的五大特性：⑴输入：一个算法有零个或多个输入。
⑵输出：一个算法有一个或多个输出。
⑶有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
⑷确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。
⑸可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
1.1.3 算法的描述方法⑴自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想注意事项：避免写成自然段欧几里德算法⑶程序设计语言优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数欧几里德算法#include <iostream.h>int CommonFactor(int m, int n) {int r=m % n;while (r!=0){m=n;n=r;r=m % n;}return n;}void main( ){cout<<CommonFactor(63, 54)<<endl;}⑷伪代码——算法语言伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。
优点：表达能力强，抽象性强，容易理解使用方法：7 ± 2欧几里德算法1. r = m % n;2. 循环直到 r 等于02.1 m = n;2.2 n = r;2.3 r = m % n;3. 输出 n ;1.1.4 算法设计的一般过程1．理解问题2．预测所有可能的输入3. 在精确解和近似解间做选择4. 确定适当的数据结构5．算法设计技术6．描述算法7．跟踪算法8．分析算法的效率9．根据算法编写代码1.2 算法分析算法分析（Algorithm Analysis）：对算法所需要的两种计算机资源——时间和空间进行估算➢时间复杂性（Time Complexity）➢空间复杂性（Space Complexity）算法分析的目的：➢设计算法——设计出复杂性尽可能低的算法➢选择算法——在多种算法中选择其中复杂性最低者时间复杂性分析的关键：➢ 问题规模：输入量的多少；➢ 基本语句：执行次数与整个算法的执行时间成正比的语句for (i=1; i<=n; i++)for (j=1; j<=n; j++)x++;问题规模：n基本语句：x++1.2.1 渐进符号1. 大O 符号定义1.1 若存在两个正的常数c 和n 0，对于任意n ≥n 0，都有T (n )≤c ×f (n )，则称T (n )=O (f (n ))2. 大Ω符号定义1.2 若存在两个正的常数c 和n 0，对于任意n ≥n 0，都有T (n )≥c ×g (n )，则称T (n )=Ω(g (n ))问题规模n 执行次3. Θ符号定义1.3 若存在三个正的常数c 1、c 2和n 0，对于任意n ≥n 0都有c 1×f (n )≥T (n )≥c 2×f (n )，则称T (n )=Θ(f (n ))例： T (n )＝5n 2＋8n ＋1当n ≥1时，5n 2＋8n ＋1≤5n 2＋8n ＋n＝5n 2＋9n ≤5n 2＋9n 2≤14n 2＝O (n 2)当n ≥1时，5n 2＋8n ＋1≥5n 2＝Ω(n 2)∴ 当n ≥1时，14n 2≥5n 2＋8n ＋1≥5n 2则：5n 2＋8n ＋1＝Θ(n 2)0问题规模n 执行次数问题规模n 执行次数定理 1.1 若T(n)=amnm +am-1nm-1 + … +a1n+a0（am>0），则有T(n)=O(nm)且T(n)=Ω(n m)，因此，有T(n)=Θ(n m)。
归并排序求逆序对什么是逆序对:设 A 为⼀个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。
如果存在正整数 i, j 使得1 ≤ i < j ≤ n ⽽且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的⼀个逆序对，也称作逆序数。
如果还是不懂请点怎么求逆序对：求逆序对就需要先介绍⼀种排序⽅法：归并排序:归并排序是利⽤归并的思想实现的排序⽅法，该算法采⽤经典的分治策略分治法将问题分成⼀些⼩的问题然后递归求解.举个例⼦：输⼊n个数，要求从⼤到⼩排序：【思路】：利⽤分治发（⼆分），从中间分开，再把左右依次分开，始终让⼩区间内的数从⼩到⼤，那么这是分治的思想（分⽽治之)图解（来⾃dreamcatcher-cs的博客）：让后利⽤⼀个新的数组把数据放过去，让后再放回来代码：#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<queue>#include<stack>#include<vector>#include<map>#include<string>#include<cstring>using namespace std;const int maxn=999999999;const int minn=-999999999;inline int read() {char c = getchar();int x = 0, f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f;}int n,a[100152],b[100250];void doit(int l,int mid,int r) {int i,j,k;int n1=mid-l+1;int n2=r-mid;int L[n1],R[n2];for (i=0; i<n1; i++)L[i]=a[l+i];for (j=0; j<n2; j++)R[j]=a[mid+j+1];i=0;j=0;k=l;while(i<n1&&j<n2) {if(L[i]<=R[j]) {a[k]=L[i];i++;} else {a[k]=R[j];j++;}k++;}while(i<n1) {a[k]=L[i];i++;k++;}while(j<n2) {a[k]=R[j];j++;k++;}}void my_sort(int l,int r) { //分if(l<r) {int mid=(l+r)/2;my_sort(l,mid);my_sort(mid+1,r);doit(l,mid,r);}}int main() {cin>>n;for(int i=0; i<n; ++i) {cin>>a[i];}my_sort(0,n-1);for(int i=0; i<n; ++i) {cout<<a[i]<<"";}return0;}接下来终于到逆序对了：放两个题⽬：【题⽬描述】Prince对他在这⽚⼤陆上维护的秩序感到满意，于是决定启程离开艾泽拉斯。
本文部分内容来自网络整理，本司不为其真实性负责，如有异议或侵权请及时联系，本司将立即删除！== 本文为word格式，下载后可方便编辑和修改！ ==归并排序实验报告篇一：归并排序与快速排序实验报告一、实验内容：对二路归并排序和快速排序对于逆序的顺序数的排序时间复杂度比较。
二、所用算法的基本思想及复杂度分析：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];int n,i;int b[3]= {1000,3000,5000};//产生3个数组。
实验名称归并排序分治策略的设计与实现实验方案实验成绩实验日期实验室信息系统设计与仿真室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
b[k++] = A[h++];
while(l <= mid) // 剩余部分1
b[k++] = A[l++];
while(h <= high) // 剩余部分2
b[k++] = A[h++];
for(i=0,j=low;i<k;i++,j++) //将排好序的数组中的数复制到原来的A[]数组中去A[j] = b[i];
}
③整个数组的分治归并
思路：利用递归思想，将整个数组分为两个（可递归排序）的子数组，然后进行归并。
void mergesort(int A[],int low,int high){
int mid; //切分点
if(low < high){// 当low小于high的时候，可继续分治
mid = (low+high)/2; //递归思想
mergesort(A,low,mid); //先分治
mergesort(A,mid+1,high);
merge(A,low,mid,high); //再归并
}
}
3、主函数设计
思路：主函数实现实验任务的基本流程。
void main()
{
int A[N],n; //定义数组A
n=input(A); //读入文件数据到数组A，返回数据个数
mergesort(A,0,n-1); //对数组A进行归并排序
output(A,n); //输出排序结果
}
四、测试
1、测试数据
下面测试数据存放在in.txt文件中，第一行表示数据个数，第二行表示数据内容。
10
10 11 2 6 9 7 4 1 3 5
2、测试结果
编码结果存放在out.txt文件中：
1 2 3 4 5 6 7 9 10 11
五、总结与讨论
1、问题与错误
2、经验与收获
3、改进与设想
六、源代码。
