李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构和算法学习--归并排序
Leefs
2020-02-03 PM
1441℃
0条
# 数据结构和算法学习--归并排序 ### 一、归并排序介绍 归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)**策略**(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案“修补”在一起,即分而治之) ### 二、归并排序思想示意图1-基本思想 ![19.归并排序算法01.png][1] ### 三、归并排序思想示意图2-合并相邻有序子序列 再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤 ![20.归并排序算法02.png][2] ![20.归并排序算法03.png][3] #### 四、归并排序的应用 给你一个数组,val arr=Array(8,4,5,7,1,3,6,2),请使用归并排序完成排序。 ```java public class MergetSort { public static void main(String[] args) { int arr[]={8,4,5,7,1,3,6,2}; 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){ if(left < right){ int mid = (left+right)/2;//中间索引 //向左递归进行分解 mergeSort(arr,left,mid,temp); //向右递归进行分解 mergeSort(arr,mid+1,right,temp); //合并 merge(arr,left,mid,right,temp); } } //合并的方法 /** * @param arr:排序的原始数组 * @param left:左边有序序列的初始索引 * @param mid:中间索引 * @param right:右边索引 * @param temp:中间数组 * */ public static void merge(int[] arr,int left,int mid,int right,int[] temp){ int i=left;//初始化i,左边有序序列的初始索引 int j=mid+1;//初始化j,邮编有序序列的初始索引 int t=0;//指向temp数组的当前索引 //(一) //先把左右两边(有序)的数据按照规则填充到temp数组 //直到左右两边的有序序列,有一边处理完毕为止 while(i<=mid&&j<=right){//继续 //如果左边的有序序列的当前元素,小于等于右边有序序列的当前元素 //即将左边的当前元素,填充到temp数组 //然后 t++,i++ if(arr[i]<=arr[j]){ temp[t]=arr[i]; t+=1; i+=1; }else{//反之,将右边有序序列的当前元素,填充到temp数组 temp[t]=arr[j]; t+=1; j+=1; } } //(二) //把有剩余数据的一边的数据依次全部填充到temp while(i<=mid){//左边的有序序列还有剩余的元素,就全部填充到temp temp[t]=arr[i]; t+=1; i+=1; } while(j<=right){//右边的有序序列还有剩余的元素,就全部填充到temp temp[t]=arr[j]; t+=1; j+=1; } //(三) //将temp数组的元素拷贝到arr //注意,并不是每次都拷贝所有 t=0; int tempLeft=left; //第一次合并 tempLeft=0,right=1 // tempLeft=2 right=3 // tL=0 ri=3 //最后一次tempLeft=0 right=7 while(tempLeft<=right){ arr[tempLeft]=temp[t]; t+=1; tempLeft+=1; } } } ``` > 运行结果 ``` [1, 2, 3, 4, 5, 6, 7, 8] ``` > 完整代码 ```java public class MergetSort { public static void main(String[] args) { //int arr[] = { 8, 4, 5, 7, 1, 3, 6, 2 }; // //测试快排的执行速度 // 创建要给80000个的随机的数组 int[] arr = new int[8000000]; for (int i = 0; i < 8000000; i++) { arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数 } System.out.println("排序前"); Date data1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(data1); System.out.println("排序前的时间是=" + date1Str); int temp[] = new int[arr.length]; //归并排序需要一个额外空间 mergeSort(arr, 0, arr.length - 1, temp); Date data2 = new Date(); String date2Str = simpleDateFormat.format(data2); System.out.println("排序前的时间是=" + date2Str); //System.out.println("归并排序后=" + Arrays.toString(arr)); } //分+合方法 public static void mergeSort(int[] arr, int left, int right, int[] temp) { if(left < right) { int mid = (left + right) / 2; //中间索引 //向左递归进行分解 mergeSort(arr, left, mid, temp); //向右递归进行分解 mergeSort(arr, mid + 1, right, temp); //合并 merge(arr, left, mid, right, temp); } } //合并的方法 /** * * @param arr 排序的原始数组 * @param left 左边有序序列的初始索引 * @param mid 中间索引 * @param right 右边索引 * @param temp 做中转的数组 */ public static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left; // 初始化i, 左边有序序列的初始索引 int j = mid + 1; //初始化j, 右边有序序列的初始索引 int t = 0; // 指向temp数组的当前索引 //(一) //先把左右两边(有序)的数据按照规则填充到temp数组 //直到左右两边的有序序列,有一边处理完毕为止 while (i <= mid && j <= right) {//继续 //如果左边的有序序列的当前元素,小于等于右边有序序列的当前元素 //即将左边的当前元素,填充到 temp数组 //然后 t++, i++ if(arr[i] <= arr[j]) { temp[t] = arr[i]; t += 1; i += 1; } else { //反之,将右边有序序列的当前元素,填充到temp数组 temp[t] = arr[j]; t += 1; j += 1; } } //(二) //把有剩余数据的一边的数据依次全部填充到temp while( i <= mid) { //左边的有序序列还有剩余的元素,就全部填充到temp temp[t] = arr[i]; t += 1; i += 1; } while( j <= right) { //右边的有序序列还有剩余的元素,就全部填充到temp temp[t] = arr[j]; t += 1; j += 1; } //(三) //将temp数组的元素拷贝到arr //注意,并不是每次都拷贝所有 t = 0; int tempLeft = left; // //第一次合并 tempLeft = 0 , right = 1 // tempLeft = 2 right = 3 // tL=0 ri=3 //最后一次 tempLeft = 0 right = 7 while(tempLeft <= right) { arr[tempLeft] = temp[t]; t += 1; tempLeft += 1; } } } ``` [1]: https://lilinchao.com/usr/uploads/2020/02/3281955173.png [2]: https://lilinchao.com/usr/uploads/2020/02/3840468971.png [3]: https://lilinchao.com/usr/uploads/2020/02/830188257.png
标签:
数据结构和算法
,
排序
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://lilinchao.com/archives/537.html
上一篇
数据结构和算法学习--希尔排序
下一篇
数据结构和算法学习--快速排序
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
47
标签云
Kafka
链表
RSA加解密
Netty
Spark Core
FastDFS
Scala
JavaScript
Shiro
Thymeleaf
SpringCloud
Java
ajax
Java工具类
CentOS
高并发
机器学习
JavaSE
Python
Spark RDD
Hadoop
序列化和反序列化
nginx
哈希表
HDFS
并发线程
排序
Spark Streaming
Java阻塞队列
Sentinel
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞