实验一 分治法合并排序

实验1、《分治算法实验》一、实验目的1. 了解分治策略算法思想2. 掌握快速排序、归并排序算法3. 了解其他分治问题典型算法二、实验内容1．编写一个简单的程序，实现归并排序。

2. 编写一段程序，实现快速排序。

3. 编写程序实现循环赛日程表。

设有n=2k个运动员要进行网球循环赛。

现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天三、算法思想分析1.归并排序先是将待排序集合分成两个大小大致相同的集合，分别对每个集合进行排序，递归调用归并排序函数，再是调用合并函数，将两个集合归并为一个排好序的集合。

2.快速排序先是选择关键数据作为比较量，然后将数组中比它小的数都放到它的左边，比它大的数放大右边，再对左右区间重复上一步，直至各个区间只有一个数。

3.循环赛日程表先将选手分为两部分，分别排序，再将两部分合并，合并时由于循环赛的规律得知直接将左上角的排序表复制到右下角，左下角的排序表复制到右上角即可。

分成两部分时需要利用递归不断分下去直至只剩下一位选手。

四、实验过程分析1．通过归并算法我对分治算法有了初步的实际操作经验，快速排序与归并算法有很大的相似点，但是在合并时的方法不一样，而循环赛日程表则是思路问题，这个题目编程难点应该在于合并时数组调用的for循环的次数以及起始位置问题。

2．对于分治算法一般是将大规模问题分解为小问题，通过递归不断分下去，然后对每个小规模用一个函数去求解。

适用于小规模独立且易解，可以合并到大问题具有最优子结构的问题。

3．归并排序和快速排序熟悉书本及PPT基本没有问题，循环赛日程表则是纠结了很久，一开始算法思路并不是十分清晰所以错了很多次，后来想了很久再观察PPT的循环赛日程表得知最终算法，编写代码中遇到了一个小问题，有一部分选手未排序，如图所示：图中有部分选手未排序，即左下角排序出现了问题，后来直接静态调试，自己按照代码用实际数据去试了一遍，发现是排序时的for循环的次数不对。

分治法-合并排序和快速排序分治法是按照以下⽅案⼯作的：将问题的实例划分为同⼀个问题的⼏个较⼩的实例，最好拥有同样的规模对这些较⼩的实例求解（⼀般使⽤递归⽅法，但在问题规模⾜够⼩的时候，有时会利⽤另⼀种算法以提⾼效率）如果必要的话，合并较⼩问题的解，以得到原始问题的解分治法的流程：4.1 合并排序合并排序是成功应⽤分治技术的⼀个完美例⼦（书上说的）。

对于⼀个需要排序的数组，合并排序把它⼀分为⼆，并对每个⼦数组递归排序，然后把这两个排好序的⼦数组合并为⼀个有序数组。

代码实现：/*** 合并排序* @author xiaofeig* @since 2015.9.16* @param array 要排序的数组* @return返回排好序的数组* */public static int[] mergeSort(int[] array){if(array.length>1){int[] subArray1=subArray(array,0,array.length/2);int[] subArray2=subArray(array,array.length/2,array.length);subArray1=mergeSort(subArray1);subArray2=mergeSort(subArray2);return merge(subArray1,subArray2);}return array;}/*** 返回指定数组的⼦数组* @author xiaofeig* @since 2015.9.16* @param array 指定的数组* @param beginIndex ⼦数组的开始下标* @param endIndex ⼦数组的结束位置（不包括该元素）* @return返回⼦数组* */public static int[] subArray(int[] array,int beginIndex,int endIndex){int[] result=new int[endIndex-beginIndex];for(int i=beginIndex;i<endIndex;i++){result[i-beginIndex]=array[i];}return result;}/*** 根据数值⼤⼩合并两个数组* @author xiaofeig* @since 2015.9.16* @param subArray1 待合并的数组* @param subArray2 待合并的数组* @return返回合并好的数组* */public static int[] merge(int[] subArray1,int[] subArray2){int[] result=new int[subArray1.length+subArray2.length];int i=0,j=0;while(i<subArray1.length&&j<subArray2.length){if(subArray1[i]>subArray2[j]){result[i+j]=subArray2[j];j++;}else{result[i+j]=subArray1[i];i++;}}if(i==subArray1.length){while(j<subArray2.length){result[i+j]=subArray2[j];}}else{while(i<subArray1.length){result[i+j]=subArray1[i];i++;}}return result;}算法分析：当n>1时，C(n)=2C(n-2)+C merge(n)，C(1)=0C merge(n)表⽰合并阶段进⾏键值⽐较的次数。

一、实验背景分治算法是一种常用的算法设计方法，其基本思想是将一个复杂问题分解成若干个相互独立的小问题，然后将小问题递归求解，最终将子问题的解合并为原问题的解。

分治算法具有高效性、可扩展性和易于实现等优点，被广泛应用于各个领域。

本实验旨在通过实现分治算法解决实际问题，掌握分治算法的设计思想，并分析其时间复杂度。

二、实验目的1. 理解分治算法的基本思想；2. 掌握分治算法的递归实现方法；3. 分析分治算法的时间复杂度；4. 应用分治算法解决实际问题。

三、实验内容本实验选择两个分治算法：快速排序和合并排序。

1. 快速排序快速排序是一种高效的排序算法，其基本思想是将待排序序列分为两个子序列，其中一个子序列的所有元素均小于另一个子序列的所有元素，然后递归地对两个子序列进行快速排序。

（1）算法描述：① 选择一个基准值（pivot），通常取序列的第一个元素；② 将序列分为两个子序列，一个子序列包含所有小于基准值的元素，另一个子序列包含所有大于基准值的元素；③ 递归地对两个子序列进行快速排序。

（2）代码实现：```cvoid quickSort(int arr[], int left, int right) {if (left < right) {int pivot = arr[left];int i = left;int j = right;while (i < j) {while (i < j && arr[j] >= pivot) {j--;}arr[i] = arr[j];while (i < j && arr[i] <= pivot) {i++;}arr[j] = arr[i];}arr[i] = pivot;quickSort(arr, left, i - 1);quickSort(arr, i + 1, right);}}```2. 合并排序合并排序是一种稳定的排序算法，其基本思想是将待排序序列分为两个子序列，分别对两个子序列进行排序，然后将排序后的子序列合并为一个有序序列。

实验1归并排序分治策略的设计与实现实验1 归并排序分治策略的设计与实现一、实验目的1、熟悉分治法求解问题的抽象控制策略；2、熟悉在顺序存储表示下求解分类问题的递归算法设计；3、通过实例转换, 掌握分治法应用。

二、实验内容1、学习分治方法的原理；2、针对分治问题设计递归算法实现归并排序算法；3、根据归并排序的递归算法改写成迭代算法。

4、测试程序与验收并进一步将程序改写成模块化可用程序。

三、实验程序的功能模块【模块】void Merge(int r[],int r1[],int s,int m,int t){ 实现数组中的已分好类的两部分进行合并 }void MergeSort(int r[],int r1[],int s,int t){ 对数组中从下标low开始到heigh结束的部分进行分类 }【递归实现】//合并数组void Merge(int r[],int r1[],int s,int m,int t)// r[]为待排序数列 r1[]用来存放排好序的数列三个int型变量 s m t ，分别为数组的最左，中间，最右{int i=s;int j=m+1;int k=s;while(i<=m && j<=t){if(r[i]<=r[j]) //左右两边的数组从头开始比，选择小者放入r1r1[k++]=r[i++];else r1[k++]=r[j++];}if(i<=m) //若比完之后，左边有剩下，依次填入r1while(i<=m)r1[k++]=r[i++];else //比完之后，右边有剩下，依次填入r1while(j<=t)r1[k++]=r[j++];for(int l=0;l<="">r[l]=r1[l];}//归并算法void MergeSort(int r[],int r1[],int s,int t){//结束归并条件，数组内只有一个元素if(s==t)r1[s]=r[s];else{int m=(s+t)/2; //规定变量m，数组中间MergeSort(r,r1,s,m); //左边归并MergeSort(r,r1,m+1,t); //右边归并Merge(r1,r,s,m,t); //合并}}【迭代实现】//合并算法sort为合并后数组，list为待合并数组，low,center,high分别为待合并数组的最左边，中间，最右边void merge(int *sort, int *list, int low, int center, int high)int i,j,k;//i,j分别代表两个小数组的最左边，通过比较，选择小者放入合并后数组for(i=low,j=(center+1),k=low; i<=center && j<=high;++k) {if(list[i] > list[j]) //若左边数组大，放右边数组未用的最左边的元素进sortsort[k] = list[j++];elsesort[k] = list[i++];}while(i<=center) //若左边数组还有元素，依次填入sortsort[k++] = list[i++];while(j<=high) //若右边数组还有元素，依次填入sortsort[k++] = list[j++];}//每次步长分组a是分组后数组，b是待分组数组，length为步长（小组长度），n为大数组总长void merge_pass(int *a, int *b, int length, int n){int i;//从数组最左边开始，按照步长分组，直到不够元素达到步长可以分组（剩最后一组）for(i=0; i<=n-2*length; i+=2*length) {int center = (i + i + 2*length - 1)/2; //定义每个小组的中间merge(a, b, i, center, i+2*length-1); //每个小组调用合并算法，最左边就是i,最右边是i+2*length-1}if((i+length)<="">int center = (i + i + 2*length - 1)/2; //定义此小组的中间merge(a, b, i, center, n-1); //调用合并算法，最右边是n-1}else //最后一个分组不够元素达到步长，复制{while(i<="" a[i]="b[i];" p="" {="">}}}//归并算法 array 为待排序数组，n为数组长度void m_sort(int *array, int n){int extra[30];int length = 1;while(length < n) //以步长为分的标准{//分组归并，结果放到extramerge_pass(extra, array, length, n);//步长增长为两倍length *= 2;//再次分组归并，结果放回arraymerge_pass(array, extra, length, n);length *= 2;}}四、递归算法改写成迭代算法的一般方法1、递归一般分为三部分，开始状态，一般状态，结束状态。

分治算法的技巧分治算法是一种常用的问题求解方法，它将复杂的问题分解成多个相同或相似的子问题，然后分别求解这些子问题，最后将子问题的解合并得到原问题的解。

在实际应用中，分治算法有一些常用的技巧可以优化解决问题的效率。

一、合并排序合并排序是分治算法的典型应用之一，它的核心思想是将待排序的数组分成两个大致相等的子数组，分别对这两个子数组进行排序，然后再将排序后的子数组合并成一个有序的数组。

在合并的过程中，有一种非常高效的方法，即“双指针法”。

该方法的基本思想是设置两个指针，分别指向待合并的两个有序数组的起始位置，然后比较两个指针所指的元素大小，将较小的元素放入新数组中，同时对应指针向后移动一位。

重复这个过程，直到其中一个指针越界，然后将另一个有序数组中剩余的元素全部放到新数组的末尾。

这种“双指针法”可以在O(n)的时间复杂度内完成合并排序的操作，因此在实际应用中非常高效。

二、快速排序快速排序是另一个典型的分治算法应用，它的基本思想是选择一个元素作为基准，将数组中比基准小的元素放在基准的左边，比基准大的元素放在基准的右边，然后对基准的左右两个子数组进行递归排序。

在快速排序的实现过程中，有一种重要的技巧叫做“分区操作”。

该操作的基本思想是通过一个游标将数组划分为两个区域，左侧的区域元素都小于等于基准，右侧的区域元素都大于等于基准。

具体实现时，可以选择数组中的第一个元素作为基准，然后设置两个指针，一个指向数组的起始位置，一个指向数组的末尾位置。

然后不断移动指针，直到左右指针相遇，将当前的元素与基准进行比较，如果小于基准，则将该元素与左侧区域的下一个位置进行交换，同时左指针向后移动一位；如果大于基准，则将该元素与右侧区域的前一个位置进行交换，同时右指针向前移动一位。

重复这个过程，直到左右指针相遇，将基准元素与指针所指的元素进行交换，这样基准就找到了最终的位置。

分区操作是快速排序算法的核心，通过合理的设计和实现可以提高算法的效率。

算法分析与设计实验报告：合并排序与快速排序一、引言算法是计算机科学中非常重要的一部分，它涉及到解决问题的方法和步骤。

合并排序和快速排序是两种经典而常用的排序算法。

本文将对这两种排序算法进行分析和设计实验，通过对比它们的性能和效率，以期得出最优算法。

二、合并排序合并排序是一种分治算法，它将原始数组不断分解为更小的数组，直到最后细分为单个元素。

然后，再将这些单个元素两两合并，形成一个有序数组。

合并排序的核心操作是合并两个有序的数组。

1. 算法步骤（1）将原始数组分解为更小的子数组，直到每个子数组只有一个元素；（2）两两合并相邻的子数组，同时进行排序，生成新的有序数组；（3）重复步骤（2），直到生成最终的有序数组。

2. 算法性能合并排序的最优时间复杂度为O(nlogn)，其中n为待排序数组的长度。

无论最好情况还是最坏情况，合并排序的复杂度都相同。

合并排序需要额外的存储空间来存储临时数组，所以空间复杂度为O(n)。

三、快速排序快速排序也是一种分治算法，它将原始数组根据一个主元（pivot）分成两个子数组，一个子数组的元素都小于主元，另一个子数组的元素都大于主元。

然后，递归地对这两个子数组进行排序，最后得到有序数组。

快速排序的核心操作是划分。

1. 算法步骤（1）选择一个主元（pivot），可以是随机选择或者固定选择第一个元素；（2）将原始数组根据主元划分为两个子数组，一个子数组的元素都小于主元，另一个子数组的元素都大于主元；（3）递归地对这两个子数组进行快速排序；（4）重复步骤（2）和（3），直到每个子数组只有一个元素，即得到最终的有序数组。

2. 算法性能快速排序的平均时间复杂度为O(nlogn)，其中n为待排序数组的长度。

最坏情况下，当每次选择的主元都是最小或最大元素时，时间复杂度为O(n^2)。

快速排序是原地排序，不需要额外的存储空间，所以空间复杂度为O(1)。

四、实验设计为了验证合并排序和快速排序的性能和效率，我们设计以下实验：1. 实验目的：比较合并排序和快速排序的时间复杂度和空间复杂度。

算法设计与分析实验报告实验名称分治法实现归并排序算法评分实验日期年月日指导教师姓名专业班级学号一.实验要求1.了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<k≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。

那末，对于这类问题分治法是十分有效的。

2.掌握分治法的一般控制流程。

DanC(p,q)global n，A[1:n]; integer m,p,q; // 1≤p≤q≤nif Small(p,q) then return G(p,q);else m=Divide(p,q); // p≤m<qreturn Combine(DanC(p,m),DanC(m+1,q));endifend DanC3．实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。

二.实验内容1.编程实现归并排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。

2.输入10组相同的数据，验证排序结果和完成排序的比较次数。

3.与复杂性函数所计算的比较次数比较。

4.用表格列出比较结果。

5.给出文字分析。

三.程序算法1. 归并排序算法procedure MERGESORT(low，high)//A(low；high)是一个全程数组，它含有high-low+1≥0个待排序的元素//integer low，high；if low<high；then mid←， //求这个集合的分割点//call MERGESORT(low，mid) //将一个子集合排序//call MERGESORT(mid+1，high) //将另一个子集合排序call MERGE(low，mid，high) //归并两个已排序的子集合// endifend MERGESORT归并两个已排序的集合procedure MERGE(low，mid，high)//A(low：high)是一个全程数组////辅助数组B(low；high)//integer h，i，j，k；h←low；i←low；j←mid+1；while h≤mid and j≤high do //当两个集合都没取尽时// if A(h)≤A(j) then B(i) ←A(h)；h←h+1else B(i) ←A(j)；j←j+1endifi←i+1repeatif h>mid thenfor k←j to high do //处理剩余的元素//B(i) ←A(k)；i←i+1repeatelse for k←h to mid doB(i) ←A(k)；i←i+1repeatendif将已归并的集合复制到Aend MERGE2. 快速排序算法QuickSort(p,q)//将数组A[1:n]中的元素A[p], A[p+1], , A[q]按不降次序排列，并假定A[n+1]是一个确定的、且大于A[1:n]中所有的数。

}
void SortableList::Input(){
for(int i=0;i<maxSize;i++){
cin>>l[i];
n++;
}
}
void SortableList::Output(){
for(int i=0;i<maxSize;i++){
cout<<l[i]<<" ";
cout<<endl;
void Input();
void Output();
private:
int *l;
int maxSize;
int n;
void MergeSort(int left,int right);
void Merge(int left,int mid,int right);
};
void SortableList::MergeSort(){
cout<<"请输入10个数："<<endl;
l.Input();
l.MergeSort();
l.Oห้องสมุดไป่ตู้tput();
}
（二）快速排序
#include<iostream.h>
class SortableList
{
public:
SortableList(int mSize){
maxSize=mSize;
2、如果采用顺序存储的可排序表作为算法实现的数据结构，则需要定义一个可排序表类SortableList，两路合并算法和快速排序算法均由定义在该类上的函数实现。其中Input函数和Output函数分别用于向可排序表中输入待排序序列，以及输出已经

合并排序是建立在归并操作上的一种有效的排序算法。

该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。

然后再把有序子序列合并为整体有序序列。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序，合并排序也叫归并排序。

1、递归实现的合并排序[cpp]view plain copy1.//2d7-1 递归实现二路归并排序2.#include "stdafx.h"3.#include <iostream>ing namespace std;5.6.int a[] = {10,5,9,4,3,7,8};7.int b[7];8.9.template <class Type>10.void Merge(Type c[],Type d[],int l,int m,int r);11.12.template <class Type>13.void MergeSort(Type a[],int left,int right);14.15.int main()16.{17.for(int i=0; i<7; i++)18. {19. cout<<a[i]<<" ";20. }21. cout<<endl;22. MergeSort(a,0,6);23.for(int i=0; i<7; i++)24. {25. cout<<a[i]<<" ";26. }27. cout<<endl;28.}29.30.template <class Type>31.void Merge(Type c[],Type d[],int l,int m,int r)32.{33.int i = l,j = m + 1,k = l;34.while((i<=m)&&(j<=r))35. {36.if(c[i]<=c[j])37. {38. d[k++] = c[i++];39. }40.else41. {42. d[k++] = c[j++];43. }44. }45.46.if(i>m)47. {48.for(int q=j; q<=r; q++)49. {50. d[k++] = c[q];51. }52. }53.else54. {55.for(int q=i; q<=m; q++)56. {57. d[k++] = c[q];58. }59. }60.}61.62.template <class Type>63.void MergeSort(Type a[],int left,int right)64.{65.if(left<right)66. {67.int i = (left + right)/2;68. MergeSort(a,left,i);69. MergeSort(a,i+1,right);70. Merge(a,b,left,i,right);//合并到数组b71.72.//复制回数组a73.for(int g=left; g<=right; g++)74. {75. a[g] = b[g];76. }77. }78.}2、合并排序非递归实现从分支策略机制入手，可消除程序中的递归。

算法设计与分析实验报告实验名称____________ 分治法实现归并排序算法___________ 评分 _____________ 实验日期______ 年______ 月 _____ 日指导教师________________________ 姓名________________ 专业班级_________________ 学号___________________一•实验要求1. 了解用分治法求解的问题：当要求解一个输入规模为n,且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<k < n,而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。

那末，对于这类问题分治法是十分有效的。

2. 掌握分治法的一般控制流程。

Da nQp,q)global n , A[1:n]; integer m,p,q; // 1 二p ii q^nif Small(p,q) then return G(p,q);else m=Divide(p,q); // p <m<qreturn Comb in e(Da nC(p,m),Da nC(m+1,q));en difend Da nC3•实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。

二•实验内容1. 编程实现归并排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。

2. 输入10组相同的数据，验证排序结果和完成排序的比较次数。

3. 与复杂性函数所计算的比较次数比较。

4. 用表格列出比较结果。

5. 给出文字分析。

三•程序算法1.归并排序算法procedure MERGESORT(low, high)〃A(low ; high)是一个全程数组，它含有high-low+1 > 0个待排序的元素//integer low , high ;if low<high ;call MERGESORT(low , mid) //call MERGESORT(mid+1 , high) // call MERGE(low , mid , high) // en dif end MERGESORT 归并两个已排序的集合procedure MERGE(low , mid , high) //A(low : high)是一个全程数组// //辅助数组 B(low ； high)//integer h ， i ， j ，k ； h J low ; i J low ; j J mid+1 ; while h < mid and j < high do // 当两个集合都没取尽时 //if A(h) w A(j) then B(i) J A(h) ; h J h+1else B(i) J A(j) ; j J j+1en dif i J i+1 repeat if h>mid the n for k J j to high do // 处理剩余的元素//B(i) J A(k) ; i J i+1repeatelse for k J h to mid doB(i) J A(k) ; i J i+1repeat en dif将已归并的集合复制到 A end MERGE2•快速排序算法 QuickSort(p,q) //将数组A[1:n]中的元素 A[p], A[p+1],... , A[q]按不降次序排列，并假定A[n+1] 是一 -个确定的、且大于 A[1: n]中所有的数。

合并排序（归并排序MergeSort）合并排序(MergeSort)是⼀种采⽤分治法策略对⼀组⽆序数据进⾏排序的算法。

分治法：将原问题划分为n个规模较⼩⽽结构与原问题相似的⼦问题；递归的解决这些⼦问题，然后合并⼦问题的结果，就得到原问题的解。

分治法在每⼀层递归上有3个步骤：分解、解决、合并。

分解(Divide)：将原问题分解为⼀系列⼦问题。

解决(Conquer)：递归的解各个⼦问题，若⼦问题⾜够⼩，则直接求解。

合并(Combine)：将⼦问题的解合并成原问题的解。

⼀、合并排序原理合并排序(MergeSort)算法完全依照了上述模式，直观的操作如下：分解：将n个元素分成各含有n/2个元素的⼦序列。

解决：⽤合并排序法对两个⼦序列递归的排序。

合并：合并两个已排序的⼦序列以得到排序结果。

⼆、合并排序算法分析合并排序采⽤分治法策略将原问题分解为k的规模较⼩的⼦问题，递归求解再合并以得到原问题的解。

合并排序所⽤的复杂性分析如下：（1）分解：这⼀步仅是计算出⼦数组中的中间位置，需要常量时间，因⽽D(n)=O(1);（2）解决：递归的解两个规模是n/2的⼦问题时间为2T(n/2)；（3）合并：我们已经注意到在⼀个含有n个元素的⼦数组上，Merge过程中的运⾏时间是O(n)，则C(n)=O(n)；整体公式为：可得：T(n)=O(nlogn) 是渐进意义下的最优算法；三、合并排序实现#include <iostream>#include <stdlib.h>#include <time.h>#define N 15using namespace std;void Merge(int * array,int low,int middle,int high);void MergeSort(int * array,int low,int high);int main(){int array[N];srand(time(0));//设置随机化种⼦，避免每次产⽣相同的随机数for(int i=0 ; i<N ; i++){array[i] = rand()%101;//数组赋值使⽤随机函数产⽣1-100之间的随机数}cout<<"排序前："<<endl;for(int j=0;j<N;j++){cout<<array[j]<<" ";}cout<<endl<<"排序后："<<endl;//调⽤合并排序函数对该数组进⾏排序MergeSort(array,0,N-1);for(int k=0;k<N;k++){cout<<array[k]<<" ";}cout<<endl;return 0;}//mainvoid MergeSort(int *array,int low,int high){if(low<high){int middle = (low+high)/2;MergeSort(array,low,middle);MergeSort(array,middle+1,high);//注意取值middle+1 ⾄ q Merge(array,low,middle,high);}//if}//MergeSortvoid Merge(int *array,int low,int middle,int high){int lSize = middle-low+1;//low⾄middle之间的数据个数int rSize = high-middle;//middle⾄high之间的数据个数int *lArray = new int[lSize];//声明左半边数组int *rArray = new int[rSize];//声明右半边数组for(int i=0;i<lSize;i++){lArray[i] = array[low+i];//为左半边数组赋值}//forfor(int j=0;j<rSize;j++){rArray[j] = array[middle+j+1];//为右半边数组赋值}//for/*a为了Array数组的循环变量，b为rArray数组的循环变量， *k为原数组array的循环变量*/int a=0,b=0,k;for(k=low;k<=high;k++){if(a>=lSize){array[k] = rArray[b++];}else if(b>=rSize){array[k] = lArray[a++];}else{if(lArray[a]<=rArray[b]){array[k] = lArray[a++];}else{array[k] = rArray[b++];}//else}//else}//for}//Merge运⾏结果：。

分治——合并排序分治策略中有⼀个经典的算法就是合并排序，这个算法的精髓也是分治⼆字，分⽽治之。

将⼀个⼤规模的问题切割成若⼲个相同的⼩问题。

⼩问题的规模⾮常⼩，⾮常easy解决，攻克了⼩的问题后再对这些⼩问题的结果进⾏合并得到⼤规模问题的解答。

合并排序便是分治策略中⽐較经典的算法，⾸先是合并。

两个排列有序的数列经过合并后成为有序的数组：代码例如以下: void _merge(int *A,int left,int middle,int right){int i=left,j=middle+1,k=0;int *C;C=new int[right-left+1];while(i<middle+1 && j<right+1){if(A[i]<A[j]){C[k++]=A[i++];}else{C[k++]=A[j++];}}while(i<middle+1)C[k++]=A[i++];while(j<right+1)C[k++]=A[j++];for(int i=0;i<right-left+1;i++){A[i+left]=C[i];}delete[] C;}上⾯的算法是将⼀个数组分成左右两个进⾏合并。

假设这左右的两个数组都是排列有序的话，那么合成的新的数列也是有序的，以下的任务就是怎么将左右的两个数列排列成有序的，⽅法就是⽤递归思想。

不断的递归，将数列不断的划分。

划分成最⼩的单元，仅仅有⼀个数的时候。

那么再进⾏合并，合并成的数列便是有序数列了，代码例如以下：void _merge_sort(int *A,int left,int right){if(left<right){int middle=(left+right)/2;_merge_sort(A,left,middle);_merge_sort(A,middle+1,right);_merge(A,left,middle,right);}}最后进⾏測试：void main(){int ib[]={2,3,1,0,9,1,3,5};int length=sizeof(ib)/sizeof(int);_merge_sort(ib,0,length-1);for(int i=0;i<length;i++){cout<<ib[i]<<' ';}}结果例如以下：。

分治法合并排序实训分治法是一种将问题分解为更小的子问题并递归解决子问题的算法。

合并排序则是一种基于分治法的排序算法。

其基本思路是将待排序的序列不断分为子序列，直到每个子序列中只有一个元素，然后不断合并子序列，直到合并成一个有序序列。

下面来进行一次分治法合并排序的实训过程。

1.划分子问题。

首先，我们将待排序的序列划分为两个子序列，分别为左子序列和右子序列。

这个划分过程可以通过计算待排序序列的中间位置来实现。

例如，若待排序序列为{3,7,1,9,5,2,8,4}，则其中间位置为4。

我们可以将序列划分为左子序列{3,7,1,9}和右子序列{5,2,8,4}。

2.解决子问题。

接下来，我们对左子序列和右子序列分别进行排序，可以使用递归算法来实现。

特别地，在划分到每个子序列只包含一个元素时，我们认为其已经排序完成。

以左子序列为例，假设其已经排序完成，得到有序序列{1,3,7,9}。

同样地，由于右子序列中有两个元素，因此我们继续将其划分为左子序列{5,2}和右子序列{8,4}，然后分别对其进行排序。

3.合并子问题。

最后，我们需要将排序完成的子序列进行合并。

对于左子序列和右子序列，可以考虑从两个序列的第一个元素开始比较。

比较后将较小的元素放到新序列的末尾，然后将该序列的指针向后移动一个元素。

例如，我们将左子序列{1,3,7,9}和右子序列{2,4,5,8}合并为一个有序序列，可以按照以下步骤进行：-分别取左子序列和右子序列的第一个元素，比较大小。

-将较小的元素放到新序列的末尾，并将该序列的指针向后移动一个元素。

-重复步骤1和步骤2，直到某一个序列的指针移到了序列的末尾。

-将剩余的元素按顺序添加到新序列的末尾。

最终得到有序序列{1,2,3,4,5,7,8,9}。

综上所述，分治法合并排序的基本思路就是将待排序序列分为子序列，分别对子序列进行排序，然后再将排序完成的子序列合并为一个有序序列。

经过不断递归，最终可以得到完整的有序序列。

实 验 比 较 实 验 得 分
附录： 完整代码（分治法）
#include<iostream> #include<time.h> #include<iomanip> using namespace std; void merge(int A[],int B[],int low,int mid,int high)
{ if(left<right) //如果序列中元素超过一个才会进行划分 { int mid=(left+right)/2; //将序列从中位数地方划分为两 个子序列 mergesort(a,b,left,mid); // 对左半边子序列递归调用自身，将子序列变成有序 mergesort(a,b,mid+1,right); //对右边子序列递归调用自 身，将子序列变成有序 merge(a,b,left,mid,right); //调用合并函数，将子序列 合并，实现整个数列的有序 for(int h=left;h<=right;h++) //将临时有序的数组复制 回原数组¦ { a[h]=b[h]; } } } void ran(int *input,int n) //数组随机生成函数 { int i; srand(time(0)); for(i=0;i<n;i++) input[i]=rand(); input[i]='\0'; } int a[1000000]; int b[1000000]; int main() { int n; cout<<"请输入要归并排序的记录个数："<<endl; for(int j=0;j<5;j++) { cin>>n; ran(a,n); //生成数组

实验报告格式如下：实验[1] [归并排序]专业学号姓名日期1 实验目的可以利用分治算法来解决排序问题2 实验内容将n个元素排成非递减顺序的序列，主要步骤是若n=1则排序终止，否则将这列元素分割成两个或是更多的子集3算法设计首先判断元素的个数，若果只有一个元素，则排序完成，如果元素的个数大于一，则进行下一步，如果给的所有元素后一项都大于前一项，或是前一项都大于后一项则排序完成，都则进行归并排序。

就以二路归并为例，首先把所有元素分成大致元素个数相等的两个子集，把已经分好的在进行分，直至不能分为止，然后进行归并，两个元素分成一组，归并是把大的元素放在右边，在对已经归并的元素在进行归并，直至完成排序4 程序代码列出你用于实验过程中所使用的程序，必须能运行，并得到你所给出的计算结果。

#include <iomanip.h>#include <iostream.h>//这个函数将b[0]至b[right-left+1]拷贝到a[left]至a[right]template <class T>void Copy(T a[],T b[],int left,int right){int size=right-left+1;for(int i=0;i<size;i++){a[left++]=b[i];}}//这个函数合并有序数组a[left:i],a[i+1:right]到b,得到新的有序数组btemplate <class T>void Merge(T a[],T b[],int left,int i,int right){int a1cout=left,//指向第一个数组开头a1end=i,//指向第一个数组结尾a2cout=i+1,//指向第二个数组开头a2end=right,//指向第二个数组结尾bcout=0;//指向b中的元素for(int j=0;j<right-left+1;j++)//执行right-left+1次循环{if(a1cout>a1end){b[bcout++]=a[a2cout++];continue;}//如果第一个数组结束，拷贝第二个数组的元素到bif(a2cout>a2end){b[bcout++]=a[a1cout++];continue;}//如果第二个数组结束，拷贝第一个数组的元素到bif(a[a1cout]<a[a2cout]){b[bcout++]=a[a1cout++];continue;}//如果两个数组都没结束，比较元素大小，把较小的放入belse{b[bcout++]=a[a2cout++];continue;}}}//对数组a[left:right]进行合并排序template <class T>void MergeSort(T a[],int left,int right){T *b=new int[right-left+1];if(left<right){int i=(left+right)/2;//取中点MergeSort(a,left,i);//左半边进行合并排序MergeSort(a,i+1,right);//右半边进行合并排序Merge(a,b,left,i,right);//左右合并到b中Copy(a,b,left,right);//从b拷贝回来}}int main(){int n;cout<<"要给多少个数据排序:";cin>>n;int *a=new int[n];cout<<"请输入数据";for(int i=0;i<n;i++)//把要排序的数据赋值给a{cin>>a[i];}MergeSort( a, 0, n-1);//调用排序for(int j=0;j<n;j++){cout<<setw(2)<<a[j];//输出排序结果}return 1;}5 运行结果你的程序的计算结果，包括图形等。

算法（分治）合并排序和快速排序⾸先说⼀下分治法的基本思想，分治法是把⼀个规模为n的问题分解为k个规模较⼩的⼦问题，这些⼦问题相互独⽴且与原问题相同（这⾥需要注意分治算法与动态规划的区别）。

递归地解这些⼦问题，然后将各⼦问题的解合并得到原问题的解。

这⾥要谈到的合并排序和快速排序便是分治算法的典型应⽤之⼀。

⾸先看合并排序，其基本思想是将待排序元素分成⼤⼩⼤致相同的2个⼦集合，分别对2个⼦集合进⾏排序，最终讲排好序的⼦集合合并成为所要求的排好序的集合。

算法⼀般通过计算两个边界的中点作为分界点，然后再递归调⽤对左半边和右半边分别合并排序，递归中⽌条件⾃然是左边界⼩于右边界，即保证⾄少有两个元素参与排序。

当⼀轮调⽤中，左半边和右半边分别排序完成后（或⽆法再划分进⾏排序后），就进⾏合并，其中对元素的真正排序便是在合并中完成的，利⽤⼀个临时数组完成对排序后数组两边元素的排序、合并。

如下是⼀个合并排序的过程图，其中S代表mergeSort函数，即递归函数，其中参数待排序数组，左分界点，右分界点；m代表merge函数，即排序、合并函数，其参数分别为待合并数组，⽬的合并数组，合并左分界点，合并中点，合并右分界点。

再来看看快速排序，其基本思想是对于输⼊的⼦数组a[p:r]，按以下3个步骤进⾏排序：1. 分解(divide)：以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. 递归求解(conquer)：通过递归调⽤快速排序算法，分别对a[p:q-1]和a[q+1:r]进⾏排序；3. 合并(merge)：由于对a[p:q-1]和a[q+1:]r的排序在分解过程中就已经完成，所以当前a[p:q-1]和a[q+1:r]中的元素都已经排好序了，⽆须再执⾏任何计算，a[p:r]就已经完成排序了。

算法之合并排序上篇⽂章讲到插⼊排序算法，是⼀个标准的增量⽅法：在排好的⼦数组后，将元素插⼊，形成新的数组。

今天要介绍的是⼀种新⽅法：分治法。

分治法，将原问题划分成n个规模较⼩⽽结构与原问题相似的⼦问题；递归地解决这些⼦问题，然后再合并其结果，就能得到原问题的解。

在每⼀层递归上都会有三个步骤：分解：将原问题分解成⼀系列⼦问题；解决：递归地解决各⼦问题，若⼦问题⾜够⼩，则直接求解；合并：将⼦问题的结果合并成原问题的解。

合并排序算法完全依照了上述模式，直观的操作如下：分解：将n个元素分成各含n/2个元素的⼦序列解决：⽤合并排序法将两个⼦序列递归的排序合并：合并两个已排序的⼦序列以得到排序结果对于⼦序列排序时，其长度为1时，递归结束。

当个元素视为已排好序。

合并过程伪代码：merge(A, p, q, r)n1=q-p+1n2=r-qL R = []for i=1->n1L[i]=A[p+i-1]for j=1>n2R[j]=A[q+j]L[n1+1]=InfinityR[n2+1]=Infinityfor k=p->rif L[i]<=R[i]A[k]=L[i]i++elseA[k]=R[j]j++合并排序伪代码：mergeSort(A, p, r)if p < rq = parseInt((p+r)/2)mergeSort(A, p, q)mergeSort(A,q+1,r)merge(A,p,q,r);js实现实例为：var ARR = [5,2,4,7,1,3,2,6];function merge(arr, p, q, r) {var n1 = q - p + 1;var n2 = r - q;var L = [];var R = [];for(var i = 1; i <= n1; i++) {L[i] = arr[p+i-1];}for(var j = 1; j <= n2; j++) {R[j] = arr[q+j];}L[n1 + 1] = Infinity;R[n2 + 1] = Infinity;i = j = 1;for(var k = p; k <= r; k++) {if(L[i] <= R[j]) {arr[k] = L[i];i++;}else {arr[k] = R[j];j++;}}return arr;}function mergeSort(arr, p, r) {if(p < r) {var q = Math.floor((p+r)/2);mergeSort(arr, p, q);mergeSort(arr, q+1, r);return merge(arr, p, q, r);}}console.log(mergeSort(ARR, 0, ARR.length-1)); 合并的过程如下所⽰：参考资料：《算法导论》。