常用的PHP排序算法以及应用场景-归并排序

作者: wxfeng 分类: php 发布时间: 2017-02-19 00:00

2、归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide
and
Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

[平均算法复杂度:O(n*log2〉n)]

图片.png

应用场景分析:归并排序和冒泡排序类似,也是稳定性比较好的一种排序算法,应用场景同样也和冒泡排序类似。不同之处在于归并算法在对大数据量进行排序时,效率会明显高于冒泡排序,这点可通过对数函数曲线n*log2〉nn*n的函数曲线中明显的观察到:

图片.png

<?php
// 归并排序:
// 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
//执行时间 3.3000000000005E-5 微秒
function Merge(&$arr, $left, $mid, $right) { 
  $i = $left; 
  $j = $mid + 1; 
  $k = 0; 
  $temp = array(); 
  while ($i <= $mid && $j <= $right) 
  { 
    if ($arr[$i] <= $arr[$j]) 
      $temp[$k++] = $arr[$i++]; 
    else 
      $temp[$k++] = $arr[$j++]; 
  } 
  while ($i <= $mid) 
    $temp[$k++] = $arr[$i++]; 
  while ($j <= $right) 
    $temp[$k++] = $arr[$j++]; 
  for ($i = $left, $j = 0; $i <= $right; $i++, $j++) 
    $arr[$i] = $temp[$j]; 

    return $arr; 
}
function MergeSort(&$arr, $left, $right) 
{ 
  if ($left < $right) 
  { 
    $mid = floor(($left + $right) / 2); 
    MergeSort($arr, $left, $mid); 
    MergeSort($arr, $mid + 1, $right); 
    Merge($arr, $left, $mid, $right); 
  } 
  return $arr;
}

$arr = ['12','65','20','22','32','52','3'];

// 记录开始时间
$time_start = microtime();

$res = MergeSort($arr,0,6);

echo "<pre>";
print_r($res);
echo "</pre>";

// 记录结束时间
$time_end = microtime();
$time = $time_end - $time_start;
 // 输出运行总时间 
echo "执行时间 $time 微秒";
?>

如果觉得我的文章对您有用,请随意赞赏。您的支持将鼓励我继续创作!

发表评论

电子邮件地址不会被公开。 必填项已用*标注