CSDN话题挑战赛第1期
活动详情地址：https://marketing.csdn.net/p/bb5081d88a77db8d6ef45bb7b6ef3d7f
参赛话题：Java学习记录 话题描述：可以记录一下平时学习Java中的一些知识点、心得、例题、常见的问题解决

好文推荐>>>🔥图文并茂详解十大排序算法让您回味无穷

目录

• 🚩合并排序(Sequencing By Merging)
• 1.百科
• 2.算法思想
• • 2.1合并过程
  • 2.2合并方法
• 3.算法描述
• 4.算法分析
• 5.构造实例
• 6.代码实现
• • 6.1 Java
  • 6.2 C/C++

🚩合并排序(Sequencing By Merging)

1.百科

合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序

2.算法思想

合并排序是采用分治策略实现对n个元素进行排序的算法，是分治法的一个典型应用和完美体现。它是一种平衡、简单的二分分治策略，其计算过程分为三大步：
（1）分解：将待排序元素分成大小大致相同的两个子序列。
（2）求解子问题：用合并排序法分别对两个子序列递归地进行排序。
（3）合并：将排好序的有序子序列进行合并，得到符合要求的有序序列

有对 分治法 不太熟悉的可以看看博主这篇文章>>>🔥分治法剖析

2.1合并过程

合并排序的关键步骤在于如何合并两个已排好序的有序子序列。为了进行合并，引入一个辅助过程Merge(A,low,middle,high)，该过程将排好序的两个子序列A[low:middle]和A[middle+1:high]进行合并。其中，low、high表示待排序范围在数组中的上界和下界，middle表示两个序列的分开位置，满足low≤middle＜high；由于在合并过程中可能会破坏原来的有序序列，因此，合并最好不要就地进行，本算法采用了辅助数组B[low:high]来存放合并后的有序序列

2.2合并方法

设置三个工作指针i，j，k。其中，i和j指示两个待排序序列中当前需比较的元素，k指向辅助数组B中待放置元素的位置。比较A[i]和A[j]的大小关系，如果A[i]小于等于A[j]，则B[k]=A[i]，同时将指针i和k分别推进一步；反之，B[k]=A[j]，同时将指针j和k分别推进一步。如此反复，直到其中一个序列为空。最后，将非空序列中的剩余元素按原次序全部放到辅助数组B的尾部

3.算法描述

语句if((!s[j])&&(dist[j]<temp))对算法的运行时间贡献最大，也是作为基本语句的原因。当外层循环标号为1时，该语句在内层循环的控制下，共执行n次，外层循环从1~n，因此，该语句的执行次数为n*n=n2，算法的时间复杂性为O(n2)
实现该算法所需的辅助空间包含为数组s和变量i、j、t和temp所分配的空间，因此，🔎Dijkstra算法的空间复杂性为O(n)

void Merge(int A[]，int low，int middle，int high){int i,j,k; int *B=new int[high-low+1];i=low; j=middle+1; k=low; while(i<=middle&&j<=high)  //两个子序列非空 if(A[i]<=A[j])  B[k++]=A[i++];     else  B[k++]=A[j++]; while (i<=middle) B[k++]=A[i++]; while (j<=high) B[k++]=A[j++];  for(i=low;i<=high;i++) A[i++]=B[i++];}

还可以用 递归形式 实现

void MergeSort (int A[]，int low，int high){    int middle; if (low<high)     {middle=(low+high)/2;   //取中点MergeSort(A,low,middle);MergeSort(A,middle+1,high); Merge(A,low,middle,high); //合并    }}

4.算法分析

当n=1时，T(n)=O(1)
当n>1时，将时间T如下分解：

1. 分解：这一步需要常量时间O(1)
2. 解决子问题：递归求解两个规模为n/2的子问题，所需时间为2T(n/2)
3. 合并：Merge算法可在O(n)时间内完成

得到合并排序算法运行时间T(n)的递归形式为
求得T(n)=nT(1)+nlogn=n+nlogn，即**合并排序算法的时间复杂性为O(nlogn)**
算法所使用的工作空间取决于Merge算法，每调用一次Merge算法，便分配一个适当大小的缓冲区，退出Merge便释放它。在最后一次调用Merge算法时，所分配的缓冲区最大，需要O(n)个工作单元。所以，合并排序算法的空间复杂性为O(n)

5.构造实例

下面给大家个图片更容易理解，合并排序就是三大步骤：分解，然后分别排序再一一合并就ok了
再给大家搞个动图

6.代码实现

6.1 Java

public static void mergeSort(int[]array){     int length=array.length;  int middle=length/2;   if(length>1){    int[]left=Arrays.copyOfRange(array,0,middle);//拷贝数组array的左半部分    int[]right=Arrays.copyOfRange(array,middle,length);//拷贝数组array的右半部分    mergeSort(left);//递归array的左半部分    mergeSort(right);//递归array的右半部分    merge(array,left,right);//数组左半部分、右半部分合并到Array  }} //合并数组，升序private static void merge(int[]result,int[]left,int[]right){   int i=0,l=0,r=0;   while(l<left.length&&r<right.length){    if(left[l]<right[r]){      result[i]=left[l];      i++;      l++;    }else{      result[i]=right[r];      i++;      r++;   }  }   while(r<right.length){//如果右边剩下合并右边的    result[i]=right[r];    r++;    i++;  }   while(l<left.length){    result[i]=left[l];    l++;    i++;  }}

6.2 C/C++

#include #include void mergesort(int*a,int length){    int step;    int*p,*q,*t;    int i,j,k,len1,len2;    int *temp; step=1;    p=a;    q=(int*)malloc(sizeof(int)*length);    temp=q;    while(step<length){ i=0; j=i+step; k=i; len1=i+step<length?i+step:length; len2=j+step<length?j+step:length; while(i<length){     while(i<len1&&j<len2){  q[k++]=p[i]<p[j]?p[i++]:p[j++];     }     while(i<len1){  q[k++]=p[i++];     }     while(j<len2){  q[k++]=p[j++];     }     i=j;     j=i+step;     k=i;     len1=i+step<length?i+step:length;     len2=j+step<length?j+step:length; } step*=2; t=p; p=q; q=t;    }     if(a!=p){ memcpy(a,p,sizeof(int)*length);    }    free(temp);}void main(void){int arrary[]={9,6,1,3,8,4,2,0,5,7};mergesort(arrary,10);}

sort(int *begin,int *end)

void sort(int *begin,int *end){int size=end-begin;int*p,*p1,*p2,*mid=begin+size/2;if(size<=1)return;//边界条件sort(begin,mid);//递归求解sort(mid,end);p=(int*)malloc(size*sizeof(int));//申请临时空间for(p1=begin,p2=mid;p1!=mid||p2!=end;)//合并有序表*p++=(p2==end||p1!=mid&&*p1<*p2)?(*p1++):(*p2++);for(p-=size;begin!=end;)//回填*begin++=*p++;free(p-size);//释放临时空间

//C++#include#includeusing namespace std;//合并排序//合并两部分有序数组time:O(n)template<typename T>void Merge(T  *arry,int start,int p,int end){    int lsize=p-start,rsize=end-p;//两个数组的大小    T * l=new T[lsize],*r=new T[rsize];//要合并的两个数组    memcpy(l,arry + start,sizeof(T)*lsize);    memcpy(r,arry + p,sizeof(T)*rsize);//将要合并的数组复制    int lnow=0,rnow=0,i;//未合并的数字的位置    for(i=0;lnow<lsize&&rnow<rsize;i++)    { if(l[lnow]>r[rnow])//取较大的数 {     arry[start+i]=l[lnow];     lnow++; } else {     arry[start+i]=r[rnow];     rnow++; }    }    if(lnow==lsize&&rnow!=rsize)//其中一个数组合并完以后，复制剩下的数据    { memcpy(arry+start+i,r+rnow,sizeof(T)*(rsize-rnow));    }    else if(rnow==rsize&&lnow!=lsize)    { memcpy(arry+start+i,l+lnow,sizeof(T)*(lsize-lnow));    }    delete l;    delete r;//清理内存    //return ;}//排序函数time:O(nlgn)template<typename T>void MergeSort(T *arry,int start,int end){    if(end-start > 1)//当元素个数为1时直接返回    { int p=(start + end)/2;//切割数组 MergeSort(arry,start,p); MergeSort(arry,p,end);//分别排序 Merge(arry,start,p,end);//合并数组    }}int main(){   int arr[10]={7,3,4,7,10,9,1,5,3,7};  MergeSort(arr,0,10);    for(int i=0;i<10;i++)    { cout<<arr[i]<<" "<<endl;    }    return 0;}

CSDN话题挑战赛第1期
活动详情地址：https://marketing.csdn.net/p/bb5081d88a77db8d6ef45bb7b6ef3d7f
参赛话题：Java学习记录 话题描述：可以记录一下平时学习Java中的一些知识点、心得、例题、常见的问题解决