图解：2-路归并排序(递归实现 )

秒速五厘米 2022-02-25 15:43 234阅读 0赞

** 划分过程：**

//划分过程
    void mergeSort(int A[],int left,int right){
    	void merge(int A[],int L1,int R1,int L2,int R2);  //声明 
    	if(left<right){
    		int mid=(left+right)/2;
    		mergeSort(A,left,mid);
    		mergeSort(A,mid+1,right);
            //合并
    		merge(A,left,mid,mid+1,right);
    	}
    }

**合并过程：**

//合并过程
    #include <stdio.h>
    const int maxn=100;
    //L2==R1+1
    void merge(int A[],int L1,int  R1,int L2,int R2){
    	int i=L1,j=L2;
    	int temp[maxn], index=0;
    	while(i<=R1&&j<=R2){
    		if(A[i]<=A[j]){
    			temp[index++]=A[i++];
    		}else{
    			temp[index++]=A[j++];
    		}
    	}
    	while(i<=R1){
    		temp[index++]=A[i++];
    	}
    	while(j<=R2){
    		temp[index++]=A[j++];
    	}
    	for(int i=0;i<index;i++){
    		A[L1+i]=temp[i]; //将合并后的序列赋值回数组A
    	}
    }

**举例实现：**

#include <stdio.h>
    const int maxn=100;
    
    //划分过程
    void mergeSort(int A[],int left,int right){
    	void merge(int A[],int L1,int R1,int L2,int R2);  //声明 
    	if(left<right){
    		int mid=(left+right)/2;
    		mergeSort(A,left,mid);
    		mergeSort(A,mid+1,right);
    		//合并 
    		merge(A,left,mid,mid+1,right);
    	}
    } 
    
    //合并过程 
    void merge(int A[],int L1,int R1,int L2,int R2){
    	int i=L1,j=L2;
    	int temp[maxn], index=0;
    	while(i<=R1&&j<=R2){
    		if(A[i]<=A[j]){
    			temp[index++]=A[i++];
    		}else{
    			temp[index++]=A[j++];
    		}
    	}
    	while(i<=R1){
    		temp[index++]=A[i++];
    	}
    	while(j<=R2){
    		temp[index++]=A[j++];
    	}
    	for(int i=0;i<index;i++){
    		A[L1+i]=temp[i];
    	}
    }
    
    
    int main(){
    	int A[7]={2,3,5,6,8,7,4};
    	mergeSort(A,0,7);
    	for(int i=0;i<7;i++){
    		printf("%d ",A[i]);
    	}
    	return 0;
    }

图解：*摘自博主(冰冻火山)*  
![Center][]

[Center]: /images/20220225/48db4deff6cd4e2cb0cbde432303f9e0.png