归并排序算法递归及循环实现

爱被打了一巴掌 2022-08-21 04:43 120阅读 0赞

第一步合并相邻长度为1的子数组段，这是因为长度为1的子数组段是已经排好序的。

用一次对数组arr的线性扫描就足以找出所有这些排好序的子数组段。然后将相邻的排好序的子数组段两两合并，构成更大的排好序的子数组段。

#include<stdio.h>
    #include<iostream>
    using namespace std;
    //递归思想归并排序 
    //void MergeSort(int a[],int left,int right){
    //	if(left<right){
    //		int i=(left+right)/2;//取中点 
    //		MergeSort(a,left,i);
    //		MergeSort(a,i+1,right);
    //		MergeSort(a,b,left,i,right);//合并到数组b 
    //		Copy(a,b,left,right);//复制会数组b	
    //	}
    //}
    
    //循环思想归并排序
    void Merge(int c[],int d[],int left,int mid,int right){
    	int i=left,j=mid+1,k=left;
    	while(i<=mid&&j<=right){
    		if(c[i]<=c[j])d[k++]=c[i++];
    		else d[k++]=c[j++];
    	}
    	if(i>mid)for(int q=j;q<=right;q++)d[k++]=c[q];//当i已经超过了mid时，说明跳出while循环时j可能<right，所以将剩余的mid~right之间的数据赋值给d数组 
    	else for(int q=i;q<=mid;q++)d[k++]=c[q]; //说明i~mid之间可能有剩余数据，将其赋值给d数组 
    }
    void MergePass(int x[],int y[],int s,int n){
    	int i=0;
    	while(i<=n-s*2){//即i+s*2<=n,以i+s为中点的左右两边的总长不能超过n 
    		Merge(x,y,i,i+s-1,i+s*2-1);
    		i=i+s*2; 
    	}
    	if(i+s<n)Merge(x,y,i,i+s-1,n-1);
    	else for(int j=i;j<=n-1;j++) y[j]=x[j];
    }
    
    
    void MergeSort(int a[],int n){
    	int b[n];
    	int s=1;
    	while(s<n){
    		MergePass(a,b,s,n);//将a->b  一次排序中的结果保存到b中 
    		s+=s;
    		MergePass(b,a,s,n);//将b->a  一次排序的结果保存到a中 
    		s+=s;
    	}
    } 
    int main(){
    		int arr[5]={23,12,2,5,3};//测试数据 
    		MergeSort(arr,5);
    		for(int i=0;i<5;i++){
    			printf("%d ",arr[i]);
    		}
    		return 0;
    }