首页 > 代码库 > 归并排序算法一窥

归并排序算法一窥

2024-07-16 14:34:17   220人阅读

归并排序法是一个基于分治法的比较排序方法，其最差情况复杂度为O(nlogn)，而快速排序法的复杂度在最差情况下达到O(n2)

本文使用PHP来讨论其算法过程：

假设对乱序数列进行排序

 $input = array(11,5,1,4,8,7,9,2);

思路可以表示：（图是PPT画的，比较简单，请看官见谅）

  1. 进行递归二分，拆成最小组合，2个数；
  2. 逐层返回，每次返回都进行合并比较；

比较的过程如下

贴上PHP代码：

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

贴上打印结果：

Array ( [0] => 11 [1] => 5 [2] => 1 [3] => 4 [4] => 8 [5] => 7 [6] => 9 [7] => 2 ) return array:Array ( [0] => 11 ) return array:Array ( [0] => 5 ) Left: Array ( [0] => 11 ) right: Array ( [0] => 5 ) compare:Array ( [0] => 11 ) Array ( [0] => 5 ) return array:Array ( [0] => 1 ) return array:Array ( [0] => 4 ) Left: Array ( [0] => 1 ) right: Array ( [0] => 4 ) compare:Array ( [0] => 1 ) Array ( [0] => 4 ) Left: Array ( [0] => 5 [1] => 11 ) right: Array ( [0] => 1 [1] => 4 ) compare:Array ( [0] => 5 [1] => 11 ) Array ( [0] => 1 [1] => 4 ) return array:Array ( [0] => 8 ) return array:Array ( [0] => 7 ) Left: Array ( [0] => 8 ) right: Array ( [0] => 7 ) compare:Array ( [0] => 8 ) Array ( [0] => 7 ) return array:Array ( [0] => 9 ) return array:Array ( [0] => 2 ) Left: Array ( [0] => 9 ) right: Array ( [0] => 2 ) compare:Array ( [0] => 9 ) Array ( [0] => 2 ) Left: Array ( [0] => 7 [1] => 8 ) right: Array ( [0] => 2 [1] => 9 ) compare:Array ( [0] => 7 [1] => 8 ) Array ( [0] => 2 [1] => 9 ) Left: Array ( [0] => 1 [1] => 4 [2] => 5 [3] => 11 ) right: Array ( [0] => 2 [1] => 7 [2] => 8 [3] => 9 ) compare:Array ( [0] => 1 [1] => 4 [2] => 5 [3] => 11 ) Array ( [0] => 2 [1] => 7 [2] => 8 [3] => 9 ) result:Array ( [0] => 1 [1] => 2 [2] => 4 [3] => 5 [4] => 7 [5] => 8 [6] => 9 [7] => 11 )
View Code

 


联系
我们