本篇文章给大家分享的是有关如何在PHP中实现一个归并排序算法,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。
归并(合并)排序法是将两个(或两个以上)有序表合并成一个新的有序表。归并排序的一个缺点是它需要存储器有另一个大小等于数据项数目的数组。如果初始数组几乎占满整个存储器,那么归并排序将不能工作,但是如果有足够的空间,归并排序会是一个很好的选择。
假设待排序的序列:
4 3 7 9 2 8 6
先说思路,归并排序的中心思想是将两个已经排序好的序列,合并成一个排序的序列。
上面的序列可以分成:
4 3 7 9
和
2,8,6
这两个序列,然后对这两个序列分别排序:结果为:
设置为序列,与序列B,
3 4 7 9
2,6,8
将上面的两个序列合并成一个排序好的序列:
合并的具体思路是:
设置两个位置指示器,分别指向序列一个与序列B开始的位置:红色为指示器指向位置:
3 4 7 9
2,6,8
比较两个指示器所指向的元素的值,将较小的插入到一个新的数组内,例如序列C,同时将对应的指示器向后移动一位:
结果为:
3 4 7 9
2,6,8
形成的序列C:已经被插入一个元素了,刚才较小的元素2。2
然后再次比较序列一个与序列B中指示器所指向的元素:将小的放入到序列C中,移动相应指针,结果为:
3 4 7 9
2,6,8
2,3
以此类推,迭代执行,直到序列一个或者序列B中某个指示器已经移到到数组末端,例如:
多次比较后,序列B已经将指示器移出到序列末端(最后一个元素之后)了。
3 4 7 9
2,6,8
2 3 4 6 7 8
然后将没有用完的序列,这里面是序列一个中其余的元素全部插入到序列C的后边即可,就剩下一个9了,将其插入到序列C后即可:
序列C结果:
2 3 4 5 6 7 8 9
这样就实现了将两个有序序列合并成一个有序序列的操作,
下面先看这个合并的php代码:
经过上面的分析和程序的实现,我们不难发现,合并已排序的序列的时间应该是线性的,就是说,最多会发生N - 1次比较,其中N是所有元素之和。
通过上面的描述,我们实现了将两个排序好的数组进行和并的过程。
此时,大家可能会有疑问,这个和归并排序整个序列有什么关系?或者你是如何能够得到最开始的两个排序好的子序列的呢?
下面,我们就来描述以下什么是归并排序,然后再看,上面的合并与归并排序的关系是如何的:
大家不妨去想,当我们需要排序如下的数组时,我们是否可以先将数组的前半部分与数组的后半部分分别进行归并排序,然后将排序的结果合并起来呢?
例如:待排序的数组:
4 3 7 9 2 8 6
先分成2部分:
4 3 7 9
2 8 6
将前半部分与后半部分分别看成一个序列,再次进行归并(就是拆分,排的序,合并)操作
就会变成:
前:
4 3
7 9
后:
2 8
,6
同样,再对每个自序列进行归并排序,再次(拆分,排的序,合并)。
当拆分的子序列内只存在一个元素(长度为1)时,那么这个序列就不必再拆分了,就是一个排序好的数组了,然后将这个序列,与其他的序列再合并到一起即可,最终就将所有的都合并好了,成为一个完整的排序好的数组。
