归并排序是一种分而治之的算法。它基于以下思想:将未排序的数组划分为多个子数组，直到每个子数组由单个元素组成，然后以产生排序数组的方式合并这些子数组。归并排序的过程步骤可以概括如下:
- 划分: 将未排序的数组划分为多个子数组，直到每个子数组只包含单个元素。
- 合并:将子数组合并为有序数组，然后合并直至获得原始数组。
- 合并技术: 考虑并比较两个子数组的第一个元素。对于升序排序，从子数组中取出值较小的元素，并成为排序数组的新元素。重复此过程，直到两个子数组都被清空并且合并后的数组成为排序数组。
示例:
为了理解归并排序，让我们考虑一个未排序的数组[4, 9, -4]（下图中第 11 个过程后创建的右侧数组）并讨论按升序对数组进行排序所采取的每个步骤。
在第一步，将数组[4, 9, -4]分为两个子数组。第一个子数组包含 [4, 9]，第二个子数组包含 [-4]。由于第一个子数组中的元素数量大于1，因此将其进一步分为分别由元素[4]和[9]组成的子数组。由于所有子数组的元素个数都是1，因此无法对数组进行进一步的划分。
在合并过程中，将上一步形成的子数组合并在一起，使用上面提到的过程形成一个排序数组。首先，将[4]和[9]子数组合并在一起，形成排序子数组[4, 9]。然后将[4, 9]和[-4]子数组合并在一起形成最终的排序数组[-4, 4, 9]
归并排序的实现
<?php
// 归并排序函数 - 分割数组
//并调用merge函数对数组进行排序和合并
//归并排序是一个递归函数
function mergesort(&$Array, $left, $right) {
if ($left < $right) {
$mid = $left + (int)(($right - $left)/2);
mergesort($Array, $left, $mid);
mergesort($Array, $mid+1, $right);
merge($Array, $left, $mid, $right);
}
}
//合并函数执行排序和合并操作
//用于归并排序函数
function merge(&$Array, $left, $mid, $right) {
// 创建两个临时数组来保存 split
//主数组的元素
$n1 = $mid - $left + 1; //LeftArray 中的元素数量
$n2 = $right - $mid; //RightArray 中的元素数量
$LeftArray = array_fill(0, $n1, 0);
$RightArray = array_fill(0, $n2, 0);
for($i=0; $i < $n1; $i++) {
$LeftArray[$i] = $Array[$left + $i];
}
for($i=0; $i < $n2; $i++) {
$RightArray[$i] = $Array[$mid + $i + 1];
}
//下面的x,y,z代表索引号
//分别为LeftArray、RightArray和Array
$x=0; $y=0; $z=$left;
while($x < $n1 && $y < $n2) {
if($LeftArray[$x] < $RightArray[$y]) {
$Array[$z] = $LeftArray[$x];
$x++;
}
else {
$Array[$z] = $RightArray[$y];
$y++;
}
$z++;
}
//复制LeftArray的剩余元素
while($x < $n1) {
$Array[$z] = $LeftArray[$x];
$x++;
$z++;
}
//复制RightArray的剩余元素
while($y < $n2) {
$Array[$z] = $RightArray[$y];
$y++;
$z++;
}
}
//打印数组的函数
function PrintArray($Array, $n) {
for ($i = 0; $i < $n; $i++)
echo $Array[$i]." ";
echo "\n";
}
//测试代码
$MyArray = array(10, 1, 23, 50, 4, 9, -4);
$n = sizeof($MyArray);
echo "原始数组\n";
PrintArray($MyArray, $n);
mergesort($MyArray, 0, $n-1);
echo "\n排序数组\n";
PrintArray($MyArray, $n);
?> 上面的代码将给出以下输出:
原始数组
10 1 23 50 4 9 -4
排序数组
-4 1 4 9 10 23 50 时间复杂度:
在所有情况下（最差、平均和最佳），归并排序始终划分数组，直到所有子数组都包含单个元素，并花费线性时间来合并这些子数组。划分过程的时间复杂度为θ(logN)，合并过程的时间复杂度为θ(N)。因此，在所有情况下，归并排序的时间复杂度都是θ(NlogN)。