美文网首页
2019-11-04 算法的个人理解 十大排序---->归并

2019-11-04 算法的个人理解 十大排序---->归并

作者: 眼睛红红红 | 来源:发表于2019-11-05 16:51 被阅读0次

闲来无事,研究下算法,发现这个算法其实比开发难度大的,首先你的理解算法的意义,其次你得有个抽象概念,其实算法最大的难点在于你怎么样通过最优的方法来实现,昨天同事问我,你知道每一个算法的使用场景吗?我当时愣住了,诚然,算法有时候写的出来,但是你未必知道它的使用场景,所以有时候研究算法还是得知道这个算法的由来,为什么要这样去做,这样做有什么优点。原来发现还有很多东西要学的,好了,不废话,今天来讲讲归并排序。

归并排序,可能很多人不熟悉,但是我说一个场景,可能很类似,最近的LOL比赛看了的同学可能明白,16支队分成四个组,然后胜者再分成两个组,最后角逐出冠军,其实这个分组,就跟归并中很类似,其实归并排序使用的是分而治之的思想来实现的,先分在合,那么怎么通过这个来实现的呢?我画了一个步骤图和代码图

先看步骤图

首先我们来模拟一个数组76948573,那么我们先来谈谈分,怎么分?我们知道首先分成两个小集合,见步骤一,将一个数组分解两个小的数组,怎么分呢?我们来看看,首先我们确定首个元素的下标 startindex和最后一个元素的小标endindex;,那么分的时候以(startindex+endindex)/2;

那么继续分,这个时候有点变化,见步骤一中左边,此时如果给左边继续分组,那么此时应该从startindex到mid这之间的元素分组,右边就是mid+1到endindex;

那么步骤二中的各个小分组继续分,那么直到每一个分组中只有一个元素为止。那么如何一直分下去直到一个元素能,

看到这里是不是有点熟悉,就是这个函数自己调用自己,没错就是递归。这个就能将原数据分组成步骤四,好了,现在分了,那么就需要比较了,怎么比较呢?

接下来我们就代码图中的1-6来对照步骤图来厘清逻辑。首先看步骤图中步骤四到步骤五,首先需要一个大集合来储存计较合并后的结果。

1------>就是创建储存结果的结果,这个数组是多大呢?就是合并的元素个数,因为index是从0开始的,所以endindex - startindex +1就是元素个数,。

2------->这三个临时变量是做什么的呢?我们看步骤五到步骤六,

首先p1记录左边集合操作的位置,p2记录右边集合位置,p记录合并后集合操作位置,在这个步骤中首先6跟右边4比较,然后再跟9比较,这个时候比较晚后发现4是最小的,这个时候将4放入大集合中第一个位置。在这一步骤操作完,p1移到7这个元素的位置,同事p2移到9元素这个位置,p移到4后面一个位置。

3-------->结合2来看,如果p1到了7元素这个位置,且p2到了9元素这个位置,说明步骤四到步骤五中的元素都互相比较完了。那么合并元素的集合将数据装入。

4,5,6--------->结合步骤图其实就是拿左边元素跟右边元素去比较。如果左边小于右边,那么先将左边放入大集合中,如果左边集合大于右边集合,那么将右边先装入大集合中

到了这里是否合并完成了呢?并没有,有一种情况就是左边元素都比右边元素小,或者左边元素都比右边元素大,那么不用比较,直接复制到大集合中

这个情况很容易漏掉的,注意此过程

最后将大集合赋值给原数组

相关文章

  • Algorithm -- 排序算法

    单链表十大经典排序算法冒泡排序选择排序插入排序归并排序快速排序堆排序计数排序桶排序 1. 十大经典排序算法 十大经...

  • 6-十大排序篇二

    十大排序(2) 今天先学习第二大类排序算法 归并排序 排序排序 希尔排序 堆排序 1.归并排序 分析:利用归并的思...

  • 排序算法概述

    十大排序算法:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序、希尔排序、计数排序,基数排序,桶排序 算法...

  • 十大排序算法

    算法说明 十大排序算法分别是:冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序...

  • 十大排序算法详解

    1. 十大排序算法 其中 冒泡,选择,归并,快速,希尔,堆排序属于比较排序 稳定性理解 如果相等的两个元素,在排序...

  • 2018-06-30

    排序算法之归并排序 归并排序算法是排序算法中的经典算法之一,其核心思想是利用归并的思想实现的排序方法,该算法采用经...

  • 数据结构和算法排序(三)

    常见十大排序算法: 冒泡排序、选择排序、插入排序、快速排序、堆排序希尔排序、归并排序、计数排序、基数排序、桶排序 ...

  • 2019-11-04 算法的个人理解 十大排序---->归并

    闲来无事,研究下算法,发现这个算法其实比开发难度大的,首先你的理解算法的意义,其次你得有个抽象概念,其实算法最大的...

  • 十大经典排序算法(java实现)

    前言 本文我们将以java代码实现十大经典排序算法,包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序...

  • 排序算法之归并排序

    归并排序(Merge Sort) 归并排序是利用归并的思想实现排序的方式,该算法采用的是经典的分治算法 归并排序过...

网友评论

      本文标题:2019-11-04 算法的个人理解 十大排序---->归并

      本文链接:https://www.haomeiwen.com/subject/dkvrbctx.html