前言:
今天朋友们对“归并排序递归思想理解”大体比较看重,看官们都想要了解一些“归并排序递归思想理解”的相关资讯。那么小编也在网络上收集了一些关于“归并排序递归思想理解””的相关内容,希望各位老铁们能喜欢,看官们快快来学习一下吧!前面的文章讲了二分查找算法,这种算法使用了一种非常常见的思想–"分治思想"。所谓分治,就是"分而治之",当解决一个大问题时,如果问题太大而无法直接解决,就可以试着把问题分解成很多个相互独立的子问题,将每个子问题各个击破,最后每个子问题得到的结果一合并就得出了原问题的结果,分治法一般都通过递归实现。本文讲解的归并排序就是分治思想的经典应用。
一.基本思想
1. 分解:给出包含若干个数的一段序列。按照分治思想要把序列分成两部分,然后对每个部分,再以相同的方式分成两个更小的序列。就这样一直分下去,到最后每段序列都只有一个数了。无法再分解了,那该怎样排序呢?答案是不用排序了,每个序列都只有一个数还怎么排序呢,换句话说,只有一个数,这本身就是有序的。这就是分治算法的妙处,把一个无序的序列分成了若干个有序的序列。
2. 合并:合并是整个排序算法的难点和重点。阐述起来很简单,就是把分开的子序列两两按序合并。
· 说起来很简单,要想真正的理解并不容易,以图解的形式描述归并的过程更直观一些。
二.图解
分解的步骤很简单。
把整个序列分成多个仅有一个数的序列后,开始合并。
第一趟合并
第二趟合并
第三趟合并
在不断合并的过程中,序列中的元素就自动排好了序。
三.具体实现
上述就是归并排序的思路,那具体是如何实现的呢?
我们要先定义一个临时数组b[],我们将被排序的数组命名为数组a[]。在两个序列合并的过程中,要先将两个序列中的元素进行比较,再按顺序存放到临时数组b[]中,这样b[]中的元素就是有序的,再将b[]中的数组复制到a[]中。以最后一次合并为例(由于合并的两序列也都经过了多次比较和合并之后才形成,所以也是有序的)
注:下文的比较过程中用的首个元素并不是序列本身的首个元素,序列本身的首个元素是固定不变的,这里的首个元素是序列中未进行比较的元素中的首个元素。
(1)第一次比较,4<7,4放入临时数组,12变成了第一个序列的首个元素。
(2)第二次比较,7<12,7放入临时数组,16变成了第二个序列的首个元素。
(3)第三次比较,12<16,12放入临时数组,13变成了第一个序列首个元素。
(4)第四次比较,13<16,13放入临时数组,50变成了第一个序列的首个元素。
(5)第五次比较,16<50,16放入临时数组,25变成了第二个序列的首个元素。
(6)第六次比较,25<50,25放进临时数组,33变成了第二个序列的首个元素。
(7)第七次比较,33<50,33放进临时数组,第二个序列的元素全部被安排了。
(8)第八次比较,发现第二个序列都比完了,这时候就把第一个序列中的剩余元素(其实也就一个了)按序放进数组。
这段过程的实现代码为
private static void Merge(int a[],int low,int mid,int high){ int[] b=new int[high-low+1];//开临时数组 int i=low,j=mid+1,t=0,t1=0;//i,j分别作为两部分的指针 while(i<=mid&&j<=high){//两部分比较,小的进临时数组 if(a[i]>a[j]){ b[t++]=a[j++]; }else { b[t++]=a[i++]; } } while(i<=mid) b[t++]=a[i++];//如果有一方元素比较完了,另一方的元素直接塞进去 while(j<=high) b[t++]=a[j++]; for(i=0;i<t;i++) a[i+low]=b[i];//临时数组的元素复制给原数组 }四.代码
import java.util.Scanner;public class Sort { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[] a=new int[n]; for(int i=0;i<n;i++){ a[i]=sc.nextInt(); } Mergesort(a,0,n-1); for(int i=0;i<n;i++){ System.out.println(a[i]); } } private static void Mergesort(int a[],int low,int high){ if(low<high){ int mid=(low+high)/2; Mergesort(a,low,mid); Mergesort(a,mid+1,high); Merge(a,low,mid,high); } } private static void Merge(int a[],int low,int mid,int high){ int[] b=new int[high-low+1]; int i=low,j=mid+1,t=0,t1=0; while(i<=mid&&j<=high){ if(a[i]>a[j]){ b[t++]=a[j++]; }else { b[t++]=a[i++]; } } while(i<=mid) b[t++]=a[i++]; while(j<=high) b[t++]=a[j++]; for(i=0;i<t;i++) a[i+low]=b[i]; }}
如果您觉得这篇文章对您有所帮助,欢迎关注我的微信公众号–【堆栈树图】,阅读更多的类似文章。如果您发现该文章有错误或不足之处,也欢迎批评指正。
标签: #归并排序递归思想理解