龙空技术网

归并排序-分治思想的典型应用

堆栈树图 42

前言:

今天朋友们对“归并排序递归思想理解”大体比较看重,看官们都想要了解一些“归并排序递归思想理解”的相关资讯。那么小编也在网络上收集了一些关于“归并排序递归思想理解””的相关内容,希望各位老铁们能喜欢,看官们快快来学习一下吧!

前面的文章讲了二分查找算法,这种算法使用了一种非常常见的思想–"分治思想"。所谓分治,就是"分而治之",当解决一个大问题时,如果问题太大而无法直接解决,就可以试着把问题分解成很多个相互独立的子问题,将每个子问题各个击破,最后每个子问题得到的结果一合并就得出了原问题的结果,分治法一般都通过递归实现。本文讲解的归并排序就是分治思想的经典应用。

一.基本思想

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];    }}

如果您觉得这篇文章对您有所帮助,欢迎关注我的微信公众号–【堆栈树图】,阅读更多的类似文章。如果您发现该文章有错误或不足之处,也欢迎批评指正。

标签: #归并排序递归思想理解