PHP 实现归并排序

浏览数：24 / 时间：2015年06月09日

在我们日常的程序开发时候，有时候需要对一个已知的集合按照一定的规则进行排序，其实当数据的规模不太大时或者数据的有序特征比较明显，其实我们可以采用其它的排序算法例如:Bubble Sort, Insertion Sort , Shell Sort 等。但是前面3中算法的共同特点是，都是从原始的列表里把元素两两取出，然后进行比较，显然冒泡排序和插入排序使用了太多的比较，在数据规模增大时，优势明显下降(主要是以每种算法的复杂度O为参考)。所以这里我们可以尝试用替代法，可以尝试将列表分成更小的子列表然后对他们排序，在排序完更小的子列表后，再将小的子列表合并成一个有序列表，这种方法就是典型的“分治法”，分而治之，逐个克服.(Divide and Conquer).

一般来说，如果一个问题太难以至于无从下手，我们可以尝试将它分成较小的子问题，然后尝试解决这些子问题，最后把这些子问题的结果合并起来。从而解决原始问题。

下图是以一个较短的数组为例来展示整个排序过程：

下面是用PHP code 实现的，以上面的元素为例，着这里主要是借用PHP的2个函数来完成的(array_slice,array_splice).

 1 <?php
 2 
 3 
 4 $input = array(6,3,2,7,1,5,8,4);
 5 
 6 
 7 function merge_sort($arr)
 8 {
 9     if(count($arr) <= 1){
10         return $arr;
11     }
12 
13     $left = array_slice($arr,0,(int)(count($arr)/2));
14     $right = array_slice($arr,(int)(count($arr)/2));
15 
16     $left = merge_sort($left);
17     $right = merge_sort($right);
18 
19     $output = merge($left,$right);
20 
21     return $output;
22 
23 }
24 
25 
26 function merge($left,$right)
27 {
28     $result = array();
29 
30     while(count($left) >0 && count($right) > 0)
31     {
32         if($left[0] <= $right[0]){
33             array_push($result,array_shift($left));
34         }else{
35             array_push($result,array_shift($right));
36         }
37     }
38 
39     array_splice($result,count($result),0,$left);
40     array_splice($result,count($result),0,$right);
41 
42     return $result;
43 
44 
45 
46 }
47 
48 
49 $output = merge_sort($input);
50 echo  "<pre>";
51 print_r($output);
52 echo  "</pre>"
53 ?>