本文共 1240 字，大约阅读时间需要 4 分钟。

递归版本

        归并排序采用了分治策略，是将一个很大的问题拆分成若干个足够小的，且性质相同的子问题，我现在要排序一个长度为10的数组，我可以将其分成两个较小的，长度为5的数组，再将长度为5的数组分为长度为2的数组，再将长度为2的数组分成长度为1的数组，长度为1的数组天然就是有序的，我在对有序的数组进行合并，直到得到有序的数组。

public class MergeSort {		public static void mergeSort(int[] arr,int left,int right) {		if(left==right) {			return;		}		int mid = left + (right-left)/2;		mergeSort(arr,left,mid);		mergeSort(arr,mid+1,right);		merge(arr,left,mid,right);	}		public static void merge(int[] arr,int left,int mid,int right) {		int[] help = new int[right - left +1];		int i = 0;		int p1 = left;		int p2 = mid+1;		while(p1<=mid && p2<=right) {			help[i++] = arr[p1]

非递归

        此时是一个长度为10的数组，如果我将它的数组中的数两个两个进行合并，它会变成五组有序的数，我再将五组两个两个进行合并，最后得到三组有序的数组，我再讲两个两个进行排序，最终得到两个有序的数组，最后再合并，得到一个有序的数组，本质上和递归过程是一样的

public static void mergeSort(int[] arr) {		if(arr==null || arr.length<2) {			return;		}		int N = arr.length;		int mergeSize = 1;//要合并的一小组的数的个数		while(mergeSize < N) {			int left = 0;//左边界			while(left < N) {				int mid = left + mergeSize -1;				if(mid>=N) {					/*					  *  如果此时的mid大于数组的长度，mid左侧是一组，右边是一组，					  *  两组之间要合并，如果mid大于N，那么说明没有左边的一组，说明					  *  已经排序完成					 */					break;				}				int right = Math.min(N-1, mid+mergeSize);				merge(arr,left,mid,right);				left = right+1;			}			mergeSize <<= 1;		}	}

转载地址：https://blog.csdn.net/weixin_58104242/article/details/122516905 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！