排序算法之归并排序

蚊子前端博客
发布于 2012-12-04 07:00
归并排序是成功应用分治技术的一个完美例子

归并排序是成功应用分治技术的一个完美例子。

分治法的思想是:

  1. 将问题的实例划分为同一个问题的几个较小的实例,最好拥有同样的规模;

  2. 对这些较小的实例求解(一般用递归方法,但在问题规模足够小的时候。有时也会利用另一个算法);

  3. 如果必要的话,合并这些较小问题的解,以得到原始问题的解。

对于一个需要排序的数组$a[0...n-1],归并排序把它一分为二:$a[0..n/2-1]和$a[n/2...n-1],并对每个子数组递归排序,然后把这两个排好序的子数组合并为一个有序数组。

下面的这个图能够很好地解释归并排序的整个流程(自己画的,有点丑)。

排序算法之归并排序-蚊子的前端博客

看上面的图,我们就知道了。递归的将一个数组分成两部分,直到小的足以解决问题就不再递归(一个数,一定是有序的)。然后再将两个有序的数组合并,最后整个数组就是有序的了。

算法如下:

COPYPHP

/** * 归并排序 * 递归调用mergeSort来对数组$a排序 * @param $a 一个可排序的数组 * @return $a 非降序排列的数组 */ function mergeSort(&$a){ $t = count($a); if($t<=1){ return; } $b = array_slice($a, 0, intval($t/2)); $c = array_slice($a, intval($t/2)); /* echo '<br/>$b: '; print_r($b); echo '<br/>$c: '; print_r($c); */ mergeSort($b); mergeSort($c); merge($b, $c, $a); /* echo "<br/>".'$a: '; print_r($a); echo "<br/>"; */ } /** * 将两个有序数组$y, $z合并为一个有序数组$x * @param $y, $z, $x * @return $x */ function merge(&$y, &$z, &$x){ $i = $j = $k = 0; $p = count($y); $q = count($z); while($i<$p && $j<$q){ if($y[$i]<$z[$j]){ $x[$k] = $y[$i]; $i++; }else{ $x[$k] = $z[$j]; $j++; } $k++; } if($i==$p){ while($j<$q){ $x[$k] = $z[$j]; $j++; $k++; } }else{ while($i<$p){ $x[$k] = $y[$i]; $i++; $k++; } } }

如果想看中间的输出结果,只需要把mergeSort()中的注释去掉就可以了。

归并排序与快排相比,归并排序是规定的排序,这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其他信息尽量按输入的顺序排列很重要,这也是它比快排有优势的地方。

标签:
阅读(273)

公众号:

qrcode

微信公众号:前端小茶馆

公众号:

qrcode

微信公众号:前端小茶馆