2-路归并排序（非递归）

你的名字 2022-02-24 02:52 214阅读 0赞

此篇只说此方法排序的难点和易错点。

#include <stdio.h>
    //合并过程 
    int maxn=1000; 
    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];
    	}
    }
    
    //防止R1，R2越界 
    int min(int a,int b){
    	if(a<=b){
    		return a;
    	}else{
    		return b;
    	}
    }
    
    //合并 
    void mergePass(int A[]){
    	void merge(int A[],int L1,int R1,int L2,int R2);//声明 
    	int min(int a,int b);
    	int n=7; //元素总数
    	//width:当前序列元素个数 
    	for(int width=1;width<=n;width=width*2){
    		for(int L1=0;L1<n;L1=L1+2*width){
    			int R1=min(L1+width-1,n-1);
    			int L2=min(R1+1,n-1);
    			int R2=min(L1+2*width-1,n-1); 
    			merge(A,L1,R1,L2,R2); 
    		} 		
    	}
    } 
    int main(){
    	int A[]={8,7,6,5,4,3,2};
    	mergePass(A);
    	for(int i=0;i<7;i++){
    		printf("%d ",A[i]);
    	}
    	return 0;
    }

既是易错点，也是难点的就是**min()函数**，很多人思考此题并没有想过这里的min(）函数作用。

在代码中min()函数用在了判断R1，和R2的下标上(待合并序列的右端点下标)。

易错的写法为：R1=L1+width-1，R2=L1+2width-1，

那么问题来了，使用min()的意义在于？

**你有没有考虑过R1，R2会越界？**  
用上述\{8，7，6，5，4，3，2\}的例子，首先来看R2。  
第一次排序后有：78  56     34  2   
继续第二次排序width==2时，在这里就能看出R2的问题了:R2显然越界了！

**那么R1又什么时候会越界呢？**  
当第四次排序width==4时候，你会惊讶的发现R1超出数组长度，  
  
**其实呢当R1越界了那么代表L2,R2也都越界了。**

本次分析到此结束。

**题外话，思考下L2其实不用使用min函数，为什么不会错误？**