归并排序用Java实现
2021/12/20 1:20:51
本文主要是介绍归并排序用Java实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
归并排序
思想
把一个的数组给分成一级一级的小组 小组内部进行排序然后几个小组进行合并再排序
用尚硅谷韩顺平老师做的图
思想简而言之就是分而治之
###代码实现
先把主函数给放上来
public static void main(String[] args) { int[] arr ={6,1,3}; int []temp = new int[arr.length]; mergeSort(arr,0,arr.length-1,temp); System.out.println(Arrays.toString(arr)); }
这个mergeSort就是来实现归并排序的方法
数组成小组
public static void mergeSort(int[] arr, int left, int right, int[] temp){ System.out.println("left是"+left+" right是"+right); //可以通过这个来看递归里面的left和right if(left <right){ int mind=(left+right)/2; mergeSort(arr,left,mind,temp); mergeSort(arr,mind+1,right,temp); }
上面的 if(left <right) 这个是很关键的
当递归到组里面只有一个数字的时候就需要退出递归了
因为你一个数字还拍啥顺序 比较数字大小起码得两个数字吧
如果只有一个数字的时候就会 left=right
老师给的图是数组有偶数个数字 那如果奇数个数分组会有一个多余的会咋办?
答案是奇数不参与最后一次分组
假如有三个数 123
第一次分组 123
第二次分组 12 和 3
到第三次分组 1 和 3(因为不满足left<right不进入if里面完成递归)
将分开的小组给合起来
这部分是最难的
这个步骤是
排序→合起来→再排序 →再合起来
直到完成
分完之后都会有左边部分和右边部分
两边分别有两个指针指着
选择两个指针指的最小的那个放到另一个数组里面
指针放完数字之后向后挪动
如果有一边已经放完了就无脑把另一半的也一个个放到另一个数组
等都放完之后把另一个数组里面排好顺序的数再放回原数组
这里再用一下尚硅谷韩顺平老师的图
首先是把左右两边的数字给按顺序放到另一个数组
public static void merge(int[] arr, int left, int mind,int right, int[] temp){ int l=left; int m=mind+1; int t=0; while(l<=mind&&m<=right){ if(arr[l]<=arr[m]){ temp[t]=arr[l]; t++; l++; } else { temp[t]=arr[m]; t++; m++; } } //注意注意注意 这上面的是把一遍的放完 //============================================== //注意注意注意 这下面的是当一遍放完之后 //把另一边给直接无脑放进去 while(l<=mind){ temp[t]=arr[l]; l++; t++; } while(m<=right){ temp[t]=arr[m]; m++; t++; } }
我们来想一下为什么当一边放完之后另一边可以无脑放
答案是因为当执行到下面的while的时候一定都是有顺序的
因为递归肯定都是执行到底之后再向上返回
上面的那个递归 递归到俩数就行了
左边一个数 右边一个数
他俩一比较一放(指放到另一个数组
)再一拿回来不就有顺序了
下面是合并的代码
int lf=left; int t1=0; System.out.println("left是"+lf+" right是"+right); while(lf<=right){ arr[lf] =temp[t1]; lf++; t1++; }
这就是从另一个数组temp把排序完的数字拿回来
这里细说一下为什么temp的t1被定义为0
因为这个空间只是用于排序的
所以它空间里面的数字被覆盖也没事
假如说排序数组有四个数字 1 2 3 4
temp的四个空间放东西的情况如下
1 2
3 4
1 2 3 4
下面是排序合并总体代码
public static void merge(int[] arr, int left, int mind,int right, int[] temp){ int l=left; int m=mind+1; int t=0; while(l<=mind&&m<=right){ if(arr[l]<=arr[m]){ temp[t]=arr[l]; t++; l++; } else { temp[t]=arr[m]; t++; m++; } } while(l<=mind){ temp[t]=arr[l]; l++; t++; } while(m<=right){ temp[t]=arr[m]; m++; t++; } int lf=left; int t1=0; System.out.println("left是"+lf+" right是"+right); while(lf<=right){ arr[lf] =temp[t1]; lf++; t1++; } }
总体代码
import java.util.Arrays; public class MergetSort { public static void main(String[] args) { int[] arr ={1,3,6}; int []temp = new int[arr.length]; mergeSort(arr,0,arr.length-1,temp); System.out.println(Arrays.toString(arr)); } public static void mergeSort(int[] arr, int left, int right, int[] temp){ System.out.println("left是"+left+" right是"+right); if(left <right){ int mind=(left+right)/2; mergeSort(arr,left,mind,temp); mergeSort(arr,mind+1,right,temp); merge(arr,left,mind,right, temp); } } public static void merge(int[] arr, int left, int mind,int right, int[] temp){ int l=left; int m=mind+1; int t=0; while(l<=mind&&m<=right){ if(arr[l]<=arr[m]){ temp[t]=arr[l]; t++; l++; } else { temp[t]=arr[m]; t++; m++; } } while(l<=mind){ temp[t]=arr[l]; l++; t++; } while(m<=right){ temp[t]=arr[m]; m++; t++; } int lf=left; int t1=0; System.out.println("left是"+lf+" right是"+right); while(lf<=right){ arr[lf] =temp[t1]; lf++; t1++; } } }
这篇关于归并排序用Java实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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学习:新手快速入门指南