归并排序(递归+非递归)
2022/1/15 23:03:34
本文主要是介绍归并排序(递归+非递归),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
递归版本
归并排序采用了分治策略,是将一个很大的问题拆分成若干个足够小的,且性质相同的子问题,我现在要排序一个长度为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]<arr[p2]?arr[p1++]:arr[p2++]; } while(p1<=mid) { help[i++] = arr[p1++]; } while(p2<=right) { help[i++] = arr[p2++]; } for(i=0;i<help.length;i++) { arr[left+i] = help[i]; } } }
非递归
此时是一个长度为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; } }
这篇关于归并排序(递归+非递归)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南