![cover](https://img-blog.csdnimg.cn/a8610d8578d7451392f7d666a279038c.gif)
【数据结构与算法】 合并排序
【包含了:合并排序(Sequencing By Merging)百科、算法思想、合并过程、合并方法、算法描述、算法分析、构造实例、代码实现、Java、C/C++】
CSDN话题挑战赛第1期
活动详情地址:https://marketing.csdn.net/p/bb5081d88a77db8d6ef45bb7b6ef3d7f
参赛话题:Java学习记录 话题描述:可以记录一下平时学习Java中的一些知识点、心得、例题、常见的问题解决
好文推荐>>>🔥图文并茂详解十大排序算法让您回味无穷
🚩合并排序(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如下分解:
- 分解:这一步需要常量时间O(1)
- 解决子问题:递归求解两个规模为n/2的子问题,所需时间为2T(n/2)
- 合并: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 <malloc.h>
#include <stdlib.h>
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<string>
#include<iostream>
using 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中的一些知识点、心得、例题、常见的问题解决
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)