闲来无事，研究下算法，发现这个算法其实比开发难度大的，首先你的理解算法的意义，其次你得有个抽象概念，其实算法最大的难点在于你怎么样通过最优的方法来实现，昨天同事问我，你知道每一个算法的使用场景吗？我当时愣住了，诚然，算法有时候写的出来，但是你未必知道它的使用场景，所以有时候研究算法还是得知道这个算法的由来，为什么要这样去做，这样做有什么优点。原来发现还有很多东西要学的，好了，不废话，今天来讲讲归并排序。
归并排序，可能很多人不熟悉，但是我说一个场景，可能很类似，最近的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--------->结合步骤图其实就是拿左边元素跟右边元素去比较。如果左边小于右边，那么先将左边放入大集合中，如果左边集合大于右边集合，那么将右边先装入大集合中
到了这里是否合并完成了呢？并没有，有一种情况就是左边元素都比右边元素小，或者左边元素都比右边元素大，那么不用比较，直接复制到大集合中
这个情况很容易漏掉的，注意此过程；
最后将大集合赋值给原数组
网友评论