PHPマージsort_phpサンプルの実装の詳細説明
- WBOYオリジナル
- 2016-12-05 13:28:181052ブラウズ
ソートのマージ方法は、2 つ (またはそれ以上) の順序付きリストを新しい順序付きリストにマージすることです。マージ ソートの欠点の 1 つは、データ項目の数と同じサイズの別の配列用のメモリが必要になることです。最初の配列がメモリのほぼ全体を占有している場合、マージ ソートは機能しませんが、十分なスペースがある場合は、マージ ソートが適切な選択肢になる可能性があります。
ソートされるシーケンスを想定します:
4 3 7 9 2 8 6
まずアイデアについて話しましょう。マージソートの中心となるアイデアは、2 つのソートされたシーケンスを 1 つのソートされたシーケンスにマージすることです。
上記のシーケンスは次のように分割できます:
4 3 7 9
そして
2 8 6
これら 2 つのシーケンスは個別にソートされ、結果は次のようになります:
シーケンス A とシーケンス B に設定します、
3 4 7 9
2 6 8
上記の 2 つのシーケンスをソートされたシーケンスにマージします。
マージの具体的なアイデアは次のとおりです:
シーケンス A とシーケンス B の開始位置をそれぞれ指す 2 つの位置インジケーターを設定します。赤色はインジケーターが指す位置です。
34、7、9
2 6 8
2 つのインジケーターが指す要素の値を比較し、小さい方の値をシーケンス C などの新しい配列に挿入し、対応するインジケーターを 1 ビット後方に移動します。
結果は次のようになります:
34、7、9
268
シーケンス C が形成されました: 1 つの要素が挿入されており、小さい方の要素 2 です。
2
次に、シーケンス A とシーケンス B のポインターが指す要素を再度比較します。小さい方をシーケンス C に入れ、対応するポインターを移動すると、結果は次のようになります。
3 4 7 9
268
2 3
以下同様に、シーケンス A またはシーケンス B のインジケーターが配列の最後に移動するまで繰り返し実行されます。例:
複数の比較の後、シーケンス B はインジケーターをシーケンスの最後 (最後の要素の後) に移動しました。
3 4 7 9
2 6 8
2 3 4 6 7 8
次に、シーケンス A の残りの要素を含むすべての未使用のシーケンスをシーケンス C の後ろに挿入します。残りの 9 は 1 つだけであり、シーケンス C に挿入できます。
このマージされた 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）时，那么这个序列就不必再拆分了，就是一个排序好的数组了。然后将这个序列，与其他的序列再合并到一起即可，最终就将所有的都合并好了，成为一个完整的排序好的数组。
程序实现：
通过上面的描述 大家应该想到，可以使用递归程序来实现这个程序设计吧：
想要实现这个程序，可能需要解决如下问题：
怎么将数组做拆分：
设定两个指示器，一个指向数组开始假定为$left，一个指向数组最后一个元素$right：
4 3 7 9 2 8 6
然 后判断 $left 是否小于$right，如果小于，说明这个序列内元素个数大于一个，就将其拆分成两个数组，拆分的方式是生成一个中间的指示器$center，值 为$left + $right /2 整除。结果为：3，然后将$left 到$center 分成一组，$center+1到$right分成一组：
4 3 7 9
2 8 6
接下来，递归的 利用$left, $center, $center+1, $right分别做为 两个序列的 左右指示器，进行操作。知道数组内有一个元素$left==$right .然后按照上面的合并数组即可：
/**
* mergeSort 归并排序
* 是开始递归函数的一个驱动函数
* @param &$arr array 待排序的数组
*/
function mergeSort(&$arr) {
$len = count($arr);//求得数组长度
mSort($arr, 0, $len-1);
}
/**
* 实际实现归并排序的程序
* @param &$arr array 需要排序的数组
* @param $left int 子序列的左下标值
* @param $right int 子序列的右下标值
*/
function mSort(&$arr, $left, $right) {
if($left < $right) {
//说明子序列内存在多余1个的元素，那么需要拆分，分别排序，合并
//计算拆分的位置，长度/2 去整
$center = floor(($left+$right) / 2);
//递归调用对左边进行再次排序：
mSort($arr, $left, $center);
//递归调用对右边进行再次排序
mSort($arr, $center+1, $right);
//合并排序结果
mergeArray($arr, $left, $center, $right);
}
}
/**
* 将两个有序数组合并成一个有序数组
* @param &$arr, 待排序的所有元素
* @param $left, 排序子数组A的开始下标
* @param $center, 排序子数组A与排序子数组B的中间下标，也就是数组A的结束下标
* @param $right, 排序子数组B的结束下标（开始为$center+1)
*/
function mergeArray(&$arr, $left, $center, $right) {
//设置两个起始位置标记
$a_i = $left;
$b_i = $center+1;
while($a_i<=$center && $b_i<=$right) {
//当数组A和数组B都没有越界时
if($arr[$a_i] < $arr[$b_i]) {
$temp[] = $arr[$a_i++];
} else {
$temp[] = $arr[$b_i++];
}
}
//判断 数组A内的元素是否都用完了，没有的话将其全部插入到C数组内：
while($a_i <= $center) {
$temp[] = $arr[$a_i++];
}
//判断 数组B内的元素是否都用完了，没有的话将其全部插入到C数组内：
while($b_i <= $right) {
$temp[] = $arr[$b_i++];
}
//将$arrC内排序好的部分，写入到$arr内：
for($i=0, $len=count($temp); $i<$len; $i++) {
$arr[$left+$i] = $temp[$i];
}
}
//do some test:
$arr = array(4, 7, 6, 3, 9, 5, 8);
mergeSort($arr);
print_r($arr);
注意上面的代码带排序的数组都使用的是 引用传递，为了节约空间。
而且，其中的合并数组的方式也为了节约空间做了相对的修改，把所有的操作都放到了$arr上完成，引用传递节约资源。
好了 上面的代码就完成了归并排序，归并排序的时间复杂度为O(N*LogN) 效率还是相当客观的。
再说，归并排序算法，中心思想是 将一个复杂问题分解成相似的小问题，再把小问题分解成更小的问题，直到分解到可以马上求解为止，然后将分解得到的结果再合并起来的一种方法。这个思想用个 成语形容叫化整为零。 放到计算机科学中有个专业属于叫分治策略（分治发）。分就是大问题变小问题，治就是小结果合并成大结果。
分治策略是很多搞笑算法的基础，我们在讨论快速排序时，也会用到分治策略的。
最后简单的说一下这个算法，虽然这个算法在时间复杂度上达到了O(NLogN)。但是还是会有一个小问题，就是在合并两个数组时，如果数组的总元素个数为 N，那么我们需要再开辟一个同样大小的空间来保存合并时的数据（就是mergeArray中的$temp数组），而且还需要将数据有$temp拷贝 会$arr，因此会浪费一些资源。因此在实际的排序中还是 相对的较少使用。