精华内容
下载资源
问答
  • 归并排序(merge-sort),是一种时间复杂度为O(nlog n)...然后我们来看一下归并排序算法:我们想把下图中的元素从小大到排序,使用归并排序算法的思想怎么做呢?是这样的,归并算法的思想是:我们可以把上面的元素...

    224a83a96f85468d0ddc55818ec7013c.png

    归并排序(merge-sort),是一种时间复杂度为O(nlog n),空间复杂度为T(n)的排序算法,发明者为大名鼎鼎的20世纪的全能通才——约翰·冯·诺依曼。

    我们先来看看O(nlog n)和O(n^2)的时间复杂度的比较:

    bb9362edb8867c1a2f153d9771f8ac17.png

    差距一目了然。。。不用说了吧。

    然后我们来看一下归并排序算法:我们想把下图中的元素从小大到排序,使用归并排序算法的思想怎么做呢?

    7d62a1557e79374ea209807dbad599c0.png

    是这样的,归并算法的思想是:我们可以把上面的元素分成两半,两半排好序,再把它们归并。

    accdb651ac6c04da573924bbc23a82ff.png

    上面这个图,我们是怎么让左边的一半和右边的一半都拍好序的呢?其实我们的思想也是又继续对半的分

    先将左右两边的那组

    元素分成一半的一半,然后再分成一半的一半,然后再分成一半一半.......就像下图这样的分,直到分到只有一个元素的时候,这时候就不能再分了。

    这时候,可以把只有一个元素的部分看成已经排好序,然后依次归并回去。

    0cb54e7676a3b46ee657eb635aba1ba3.png

    080eeec48d0f03875b23ac859d1e5c2d.png

    c42a6096f11b8d00e3d0ddff37f9ffe3.png

    下面我们来看:

    9fb4eef0e2d45a958f6bfe370206b562.png

    上图有8个元素,分到不能再分,最底层是第3层(从0开始),找规律可得其实就是8/2,8/2/2,8/2/2/2,也就是log以2为底8的对数层,那么有N个元素,就是log(N)层

    ec07e90628ed8948e45c64be690c3c4d.png

    总之,当元素有N个的时候,这个层数就是log(N)这样的数量级的,在这种情况下,我们要处理的数量级都是一样的N,虽然我们把它分成了不同的部分。

    52b2a0b3ef6268268aa4a04cee2181c4.png

    到上面这里,我们又怎么让左右两边的元素归并呢?看着虽然简单,但是代码不简单啊。。。。天才的世界就是不一样。

    我们不能再像冒泡排序、插入排序,选择排序那样的判断交换位置了,而是需要开辟一个新的一毛一样和原来的数组元素一样大的空间来辅助我们完成归并排序。

    使用了临时空间,归并的过程将变得非常容易。。。。(( ╯□╰ ))

    7ea857918213fd6487a56f65e88bd65e.png

    然后,我们需要使用3个索引,用于指向不同的位置

    9a962bfb07e6e71aeb9ae5b2d1fbf720.png

    a20270d57e376e29a75d60a9eff54b6c.png

    我们左边和右边的两个索引对应的元素比较大小,小的放入临时空间中,同时,移动指针

    1de891f8f5ab059e765a371e0d5b5463.png

    重复上面的过程就可以完成了归并排序

    下面是Java代码的实现(主要代码):

    49328f40f82473d51952a413b0351d32.png

    merge(arr,l,mid,r)归并方法:

    05c7a74104cdbfe8371523118c906fcb.png

    d8b19acea587fa4432844cb0135a7d8c.png

    4ada54f219d743b5eed56a9d42e6235e.png

    当我们的元素像上图这样的话,可能左边已经归并好,右边还没有好,防止索引越界之后一序列问题,这时候我们就需要判断了

    05f1806137b257366e2dfafbea5fff6c.png

    同理,也有可能右边已经归并好了,左边的没有好

    时间复杂度分析,一共有log(N)层,每层的元素都一样都是N,我们在归并过程中,每层都归并N次,也就是时间复杂度为O(nlog n),空间复杂度为T(n)

    以后再补充吧,有的地方还是不太懂,慢慢来咯,比如优化方面,还有其他的( ╯□╰ )

    展开全文
  • 归并排序(merge-sort),是一种时间复杂度为O(nlog n)...然后我们来看一下归并排序算法:我们想把下图中的元素从小大到排序,使用归并排序算法的思想怎么做呢?是这样的,归并算法的思想是:我们可以把上面的元素...

    6c350438d08ee25daec17eac63d5594d.png

    归并排序(merge-sort),是一种时间复杂度为O(nlog n),空间复杂度为T(n)的排序算法,发明者为大名鼎鼎的20世纪的全能通才——约翰·冯·诺依曼。

    我们先来看看O(nlog n)和O(n^2)的时间复杂度的比较:

    6b82fd24ea8deaf77b3bfb78bd02a413.png

    差距一目了然。。。不用说了吧。

    然后我们来看一下归并排序算法:我们想把下图中的元素从小大到排序,使用归并排序算法的思想怎么做呢?

    764706a109c5f05b5fff7af8959e9486.png

    是这样的,归并算法的思想是:我们可以把上面的元素分成两半,两半排好序,再把它们归并。

    1436e3349a4df1c347e29071cf27d6df.png

    上面这个图,我们是怎么让左边的一半和右边的一半都拍好序的呢?其实我们的思想也是又继续对半的分

    先将左右两边的那组

    元素分成一半的一半,然后再分成一半的一半,然后再分成一半一半.......就像下图这样的分,直到分到只有一个元素的时候,这时候就不能再分了。

    这时候,可以把只有一个元素的部分看成已经排好序,然后依次归并回去。

    301b4baf52561e30702eb48d420a046e.png

    56360a167db93520db1b4baa6cda9f2e.png

    ed6c858f9cde1730cd245f2898c52eef.png

    下面我们来看:

    02ef5a3025d4d52a4ae3e451a77288ca.png

    上图有8个元素,分到不能再分,最底层是第3层(从0开始),找规律可得其实就是8/2,8/2/2,8/2/2/2,也就是log以2为底8的对数层,那么有N个元素,就是log(N)层

    18a5d4900e8d58c4b3586580524167e0.png

    总之,当元素有N个的时候,这个层数就是log(N)这样的数量级的,在这种情况下,我们要处理的数量级都是一样的N,虽然我们把它分成了不同的部分。

    89615e9a849be1d747bcd7f5baf16928.png

    到上面这里,我们又怎么让左右两边的元素归并呢?看着虽然简单,但是代码不简单啊。。。。天才的世界就是不一样。

    我们不能再像冒泡排序、插入排序,选择排序那样的判断交换位置了,而是需要开辟一个新的一毛一样和原来的数组元素一样大的空间来辅助我们完成归并排序。

    使用了临时空间,归并的过程将变得非常容易。。。。(( ╯□╰ ))

    e26b680e1a8f98c6e834bccc9b862557.png

    然后,我们需要使用3个索引,用于指向不同的位置

    04d340a9f3c8d0d4f1f5c54c6b4b051d.png

    d657ea4497838eacfc6cc901c8b6b838.png

    我们左边和右边的两个索引对应的元素比较大小,小的放入临时空间中,同时,移动指针

    db9a8f97355cf306f45b0baa87c3378b.png

    重复上面的过程就可以完成了归并排序

    下面是Java代码的实现(主要代码):

    c2c7c324532fd12c34a794fd56ff1f96.png

    merge(arr,l,mid,r)归并方法:

    86b966e40247e5c555cc53a0d7cef2d6.png

    9f3df1cd8c23aac3cb28aeb41abc1149.png

    c4b15d46d96c0fa28ed05cfea36c9a57.png

    当我们的元素像上图这样的话,可能左边已经归并好,右边还没有好,防止索引越界之后一序列问题,这时候我们就需要判断了

    6684526ac77b19b6224fd99eac4f0409.png

    同理,也有可能右边已经归并好了,左边的没有好

    时间复杂度分析,一共有log(N)层,每层的元素都一样都是N,我们在归并过程中,每层都归并N次,也就是时间复杂度为O(nlog n),空间复杂度为T(n)

    以后再补充吧,有的地方还是不太懂,慢慢来咯,比如优化方面,还有其他的( ╯□╰ )

    展开全文
  • 归并排序法详解

    2016-03-05 21:15:28
    1.归并排序法的思想及分段代码  归并排序法顾名思义是一种排序的算法,它是分而治之(divide-and-conquer)这种思想的典型体现。从名字上我们可以很清楚的知道这是一种通过归并实现数列有序的算法。算法图解如下: ...

    1.归并排序法的思想及分段代码

               归并排序法顾名思义是一种排序的算法,它是分而治之(divide-and-conquer)这种思想的典型体现。从名字上我们可以很清楚的知道这是一种通过归并实现数列有序的算法。算法图解如下:


           那么什么是归并呢?归并从数列的操作上可以表示为:首先将一个需要排序的数列进行二分操作,接着对二分后的数列接着进行二分,直到每一个元素作为一个子序列,这体现了分而治之的“分”字诀。然后对相邻的两个子序列进行排序,排序完成后再对它二分前的子序列进行排序,以此类推,一步一步的完成整个排序工作。数列分割的代码如下:

    void mergesort(int first,int last )//对已知数组进行分解
    {
        int middle;
        if(first<last)
    	{
    	    middle=(first+last)/2;
    	    mergesort(first,middle);//左边分解
    	    mergesort(middle+1,last);//右边分解
    	    merge_sort(a,first,middle,last);//排序合并数组
    	}
    }

           排序的具体思想是:将有序数列a[i]~a[j]的第一个元素a[i]和有序数列a[j+1]~a[k]的第一个元素a[j+1]进行大小比较,将较小的元素输入到b[m](int m=i),将剩下的两个数列的首元比较大小,小的储存到b[m+1]中,以此类推直到一个数列的元素安全储存到数列b中,再将剩下的那个有序数列依次储存到b中。这就体现了分而治之的“治”字诀。数列排序的代码如下:

    void merge_sort(int b[ ],int first,int middle,int last)
    {
       int temp[num];
       int i,j,k;
       i=first;
       k=first;
       j=middle+1;
       while(i<=middle&&j<=last)
       {
           if(b[i]<=b[j]) temp[k++]=b[i++];
           else temp[k++]=b[j++];
       }
       while(i<=middle)
       {
           temp[k++]=b[i++];
       }
       while(j<=last)
       {
          temp[k++]=b[j++];
       }
       for(int i=first;i<=last;i++)
       {
           a[i]=temp[i];
       }
    
    }
    2.整个代码如下

    #include<iostream>
    using namespace std;
    
    /**************************归并排序******************************/
    const static int num=9;//数组的维数
    static int * a;
    
    
    void merge_sort(int b[ ],int first,int middle,int last)
    {
       int temp[num];
       int i,j,k;
       i=first;
       k=first;
       j=middle+1;
       while(i<=middle&&j<=last)
       {
    	if(b[i]<=b[j]) temp[k++]=b[i++];
    	else temp[k++]=b[j++];
       }
       while(i<=middle)
       {
           temp[k++]=b[i++];
       }
       while(j<=last)
       {
          temp[k++]=b[j++];
       }
       for(int i=first;i<=last;i++)
       {
           a[i]=temp [i];
       }
    
    }
    void mergesort(int first,int last )//对已知数组进行分解
    {
        int middle;
        if(first<last)
    	{
    	    middle=(first+last)/2;
    	    mergesort(first,middle);//左边分解
    	    mergesort(middle+1,last);//右边分解
    	    merge_sort(a,first,middle,last);//排序合并数组
    	}
    }
    int main()
    {
       a=new int[num];
       for(int i=0;i<num;i++)
       {
           cin>>a[i];
       }
       mergesort(0,num-1);
       for(int i=0;i<num;i++)
       {
            cout<<a[i]<<" ";
       }
       system("pause");
       return 0;
    }
         这就是整个程序的代码,只要能理解归并的思想,同时将递归加入到程序中,编出这个代码就会变得so easy!

    展开全文
  • 前面的文章讲了二分查找算法,这种算法使用了一种非常常见的思想–“分治思想”。...本文讲解的归并排序就是分治思想的经典应用。一.基本思想分解:给出包含若干个数的一段序列。按照分治思想要...

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

    一.基本思想

    1. 分解:给出包含若干个数的一段序列。按照分治思想要把序列分成两部分,然后对每个部分,再以相同的方式分成两个更小的序列。就这样一直分下去,到最后每段序列都只有一个数了。无法再分解了,那该怎样排序呢?答案是不用排序了,每个序列都只有一个数还怎么排序呢,换句话说,只有一个数,这本身就是有序的。这就是分治算法的妙处,把一个无序的序列分成了若干个有序的序列。
    2. 合并:合并是整个排序算法的难点和重点。阐述起来很简单,就是把分开的子序列两两按序合并。
    • 说起来很简单,要想真正的理解并不容易,以图解的形式描述归并的过程更直观一些。

    二.图解

    分解的步骤很简单。

    10b3bc5984dc3c7eeb33d02a88f95348.png

    把整个序列分成多个仅有一个数的序列后,开始合并。

    第一趟合并

    5a1146d3fd8e01fe158b847fe06c3230.png

    第二趟合并

    4d7b5e990326149fa3cee62f095a112d.png

    第三趟合并

    51b16458ce2499da1f03710e4a686f2c.png

    在不断合并的过程中,序列中的元素就自动排好了序。

    三.具体实现

    上述就是归并排序的思路,那具体是如何实现的呢?

    我们要先定义一个临时数组b[],我们将被排序的数组命名为数组a[]。在两个序列合并的过程中,要先将两个序列中的元素进行比较,再按顺序存放到临时数组b[]中,这样b[]中的元素就是有序的,再将b[]中的数组复制到a[]中。以最后一次合并为例(由于合并的两序列也都经过了多次比较和合并之后才形成,所以也是有序的)

    注:下文的比较过程中用的首个元素并不是序列本身的首个元素,序列本身的首个元素是固定不变的,这里的首个元素是序列中未进行比较的元素中的首个元素。

    (1)第一次比较,4<7,4放入临时数组,12变成了第一个序列的首个元素。

    bdd5d56f4d28a87dd8934b124d2b3841.png

    (2)第二次比较,7<12,7放入临时数组,16变成了第二个序列的首个元素。

    6258dbecfba4fdcb6524c997fc2d6335.png

    (3)第三次比较,12<16,12放入临时数组,13变成了第一个序列首个元素。

    ca349a95629860c8e51d9408b41d150f.png

    (4)第四次比较,13<16,13放入临时数组,50变成了第一个序列的首个元素。

    1fe97762615e3fa8ace51bcb4d5d03ed.png

    (5)第五次比较,16<50,16放入临时数组,25变成了第二个序列的首个元素。

    790d60fa5a784d70c2dd53e9038dfb1b.png

    (6)第六次比较,25<50,25放进临时数组,33变成了第二个序列的首个元素。

    426d53d614aa181438dfd6c312deb55d.png

    (7)第七次比较,33<50,33放进临时数组,第二个序列的元素全部被安排了。

    6742fa71fa286db0161b5b4d79492581.png

    (8)第八次比较,发现第二个序列都比完了,这时候就把第一个序列中的剩余元素(其实也就一个了)按序放进数组。

    f2dc0cf61929e7db65967dc296a919d8.png

    这段过程的实现代码为

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

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

    展开全文
  • 归并排序法

    2020-03-24 20:46:56
    归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治策略。 import java.text.SimpleDateFormat; import java.util.Date; public class MergetSort { public static void main(String[]...
  • 图解归并排序法

    2020-03-14 12:04:11
    归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补...
  • 文章目录5、归并排序法6、基数排序法7、堆排序法 (不稳定) 5、归并排序法 归并排序是利用归并的思想实现的排序方法。如上图。思路比较简单,就是对数组进行不断的分割,分割到只剩一个元素,然后,再两两合并起来。...
  • 本文讲解的归并排序就是分治思想的经典应用。 一.基本思想 分解:给出包含若干个数一段序列。按照分治思想要把序列分成两部分,然后对每个部分,再以相同方式分成两个更小序列。就这样一直分下去,到最后每...
  • 归并排序(Merge sort)是建立在归并操作上一种有效排序算法。该算法是采用分治(Divide and Conquer)一个非常典型应用。
  • 归并排序归并排序(英语:Merge sort,或mergesort),是创建在归并操作上一种有效排序算法。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治(Divide and Conquer)一个非常典型应用,且各层分治...
  • 归并排序的思想

    2013-05-21 23:25:51
    归并排序是建立在归并操作上一种有效排序算法。该算法是采用分治(Divide and Conquer)一个非常典型应用。 将已有序子序列合并,得到完全有序序列;即先使每个子序列有序,再使子序列段间有序。若...
  • 归并排序法 - Merge Sort 文章目录归并排序法 - Merge Sortnlogn 比 n^2 快多少?归并排序设计思想时间、空间复杂度归并排序...O(n*log n)排序算法 归并排序法 - Merge Sort nlogn 比 n^2 快多少? 测试用例太少...
  • 作为一种典型分而治之思想的算法应用,归并排序的实现由两种方法: 自上而下递归(所有递归方法都可以用迭代重写,所以就有了第 2 种方法); 自下而上迭代; 在《数据结构与算法 JavaScript 描述》中,作者...
  • 归并排序法 注:学习心得,仅供参考。如有错误,请不吝指教。 基本原理 归并排序指是将两个已经排序序列合并为一个序列操作。其具体思想为:(假设序列共有n个元素) 1:将序列每相邻两个数字进行...
  • 这个有序对称为 A 一个逆序对,也称作逆序数。 求解一个数组中逆序对个数 其实就是求下标小大数,那么二话不说先来暴力,暴力显然是O(n2),8太行 int unseq(vector<int> &nums) { int...
  • 归并排序思想

    2014-02-24 21:22:49
    该算法是采用分治(Divide and Conquer)一个非常典型应用,归并排序将两个已排序表合并成一个表。   归并排序基本原理 通过对若干个有序结点序列归并来实现排序。 所谓归并是指将若干个已排好...
  • 外部排序法: 数据量过大,无法全部加载到内存中,需要借助外部存储(文件等)进行排序。 常见排序算法分类 一、(Quick Sort)基本概念 1.基本介绍 快速排序(Quicksort)是对冒泡排序一种改进。基本思想是:...
  • 算法思想:分治实际问题:归并排序编写语言:JavaJava代码//本篇博文代码是递归方式归并排序算法实现public class MergeSort{public static void main(String[] args){int[] ary = new int[] {1, 3, 4, 5, 2, 7,...
  • 归并排序是建立在归并操作上一种有效排序算法,该算法是采用分治(Divide and Conquer)一个非常典型应用。将已有序子序列合并,得到完全有序序列;即先使每个子序列有序,再使子序列段间有序。若将两...
  • 常用排序算法——归并排序法

    千次阅读 2013-12-27 10:11:38
    归并排序采用是分治思想,将数组不断分解为子数组,直到子数组只有一个元素,每次分解对应一个归并函数,归并函数可以将当前分解两个子数组合并起来。有两种方式可以实现归并排序,第一种是递归方式实现,代码...
  • 一. 基本思想 ... * 归并排序 O(Nlog(N)) * 需要将当前数组拷贝一份出来,因此相比之前排序,需要更多存储空间 */ public class MergeSort { /** * 将arr[l...mid]和arr[mid+1......
  • 什么是分治: 在计算机科学中,分治是建基于多项分支递归一种很重要算法范式。... 这个技巧是很多高效算法基础,如排序算法(快速排序、归并排序)、傅立叶变换(快速傅立叶变换)。 另一方面,理解...
  • 核心思想:归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治策略(分治将问题分成一些小的问题然后递归求解,而治的阶段则将分的阶段得到的各答案”修补”在一起,即分而治之)。 如图:对于有序的两...
  • 距离上次写快排算法文章已经过去一个半月了,和本文要提到的归并排序算法类似,快排也是分治思想的一种典型应用,如果有不熟悉快速排序同学可以翻阅我之前写过的的快速排序算法文章。分治算法首先为大家介绍...
  • 这些算法典型地遵循分治法的思想:将原问题分解为几个规模较小但是类似于原问题的子问题,递归求解这些子问题, 然后再合并这些问题的解来建立原问题的解。分治法在每层递归时有三个步骤:分解原问题为若干子问题,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,955
精华内容 782
关键字:

归并排序法的思想