归并排序算法解析（详细解析）

比眉伴天荒 2023-10-11 16:29 48阅读 0赞

归并排序算法简单来说是：先分解，后合并。

分解：使用二分递归法进行分解，直到分解到最后只剩一个元素的时候开始回退。

合并：进行递归逐步回退并进行排序。

直接上代码吧，代码最能直观的看出来：

java版本：

//java版本
    
    package SuanFa;
    import java.util.Scanner;
    public class merge_sort {
        static int N=100;
        static int temp[] = new int[100];//辅助数组，先把排好序的元素送到temp，然后在复制到原数组a
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n= in.nextInt();
            int a[]=new int[N];
            for(int i=0;i<n;i++)
            {
                a[i]=in.nextInt();
            }
            print(a,n);
            mergesort(a,0,n-1);
            print(a,n);
        }
    //打印原数组内的数据
        public static void print(int a[],int n)
        {
            for(int i=0;i<n;i++)
            {
                System.out.printf("%d ",a[i]);
            }
            System.out.println();
        }
    //归并排序的入口
        public static void mergesort(int a[],int begin,int end)
        {
            int mid;
            if(begin<end)
            {
                mid=(begin+end)/2;//进行二分，把数据分成一段一段的
                mergesort(a,begin,mid);//左序列二分
                mergesort(a,mid+1,end);//右序列二分
                merge(a,begin,mid,end);//二分数据进行合并
            }
        }
    //归并排序算法
        public static void merge(int a[],int begin,int mid,int end) {
    
            int i = begin;//左序列第一个未排序的元素
            int j = mid + 1;//右序列第一个未排序的元素
            int k = begin;//辅助数组的第一个元素下标
            while (i <= mid && j <= end) {
                if (a[i] < a[j]) {
                    temp[k++] = a[i++];
                } else {
                    temp[k++] = a[j++];
                }
            }
    //因为二分到最后的时候仅有一个元素，当我们合并到最后剩余的元素是有顺序的
    //所以我们在最后的时候，只需要把左边剩余的元素挂在后面，把右边的元素挂在后面即可
            while (i <= mid)//合并左半区剩余的元素
                temp[k++] = a[i++];
            while (j <= end)//合并右半区剩余的元素
                temp[k++] = a[j++];
    //把temp数组内的元素复制到原数组中
            while (begin <= end) {
                a[begin] = temp[begin];//切忌这里不能是a[begin++]=temp[begin++],因为这样begin会+两次
                begin++;
            }
        }
    }

c++版本：

//c++版本
    #include<bits/stdc++.h>
    #define N 100
    using namespace std;
    void print(int arr[],int n) {
    	for(int i=0; i<n; i++) {
    		printf("%d ",arr[i]);
    	}
    	printf("\n");
    }
    //合并
    void merge(int arr[],int tempArr[],int left,int mid,int right) {
    	//标记左半区第一个未排序的元素
    	int l_pos=left;
    	//标记右半区第一个未排序的元素
    	int r_pos=mid+1;
    	//临时数组的下标
    	int pos=left;
    	//合并
    	while(l_pos<=mid&&r_pos<=right) {
    		if(arr[l_pos]<arr[r_pos]) {
    			tempArr[pos++]=arr[l_pos++];
    		} else {
    			tempArr[pos++]=arr[r_pos++];
    		}
    	}
    	//合并左半区剩余的元素
    	while(l_pos<=mid) {
    		tempArr[pos++]=arr[l_pos++];
    	}
    
    	//合并右半区剩余的元素
    	while(r_pos<=right) {
    		tempArr[pos++]=arr[r_pos++];
    	}
    	//把临时数组内的元素复制到原来的数组
    	while(left<=right) {
    		arr[left]=tempArr[left];
    		left++;
    	}
    
    }
    
    //归并排序
    void msort(int arr[],int tempArr[],int left,int right) {
    	//如果只有一个元素，那么就不需要继续划分
    	//只有一个元素的区域，本身就是有序的，只需要被归并计科
    	if(left<right) {
    		int mid=(left+right)/2;
    		//递归左序列，继续划分
    		msort(arr,tempArr,left,mid);
    		//递归划分右半区域
    		msort(arr,tempArr,mid+1,right);
    		//合并已经排序的左右半区
    		merge(arr,tempArr,left,mid,right);
    	}
    }
    
    
    //归并排序的入口
    void merge_sort(int arr[],int n) {
    	//分配一个辅助数组
    	int* tempArr=(int*)malloc(n * sizeof(int));
    	if(tempArr) { //辅助数组分配成功
    		msort(arr,tempArr,0,n-1);
    		free(tempArr);
    	} else {
    		printf("error: failed to allocate memory");
    	}
    }
    int main() {
    	int n=0,arr[N];
    	scanf("%d",&n);
    	for(int i=0; i<n; i++) {
    		scanf("%d",&arr[i]);
    	}
    	print(arr,n);
    	merge_sort(arr,n);
    	print(arr,n);
    
    }