7967 - PHP数组排序算法：合并算法

admin

1. <?php
   
2. 
   
3.         //PHP数组排序算法：合并算法
   
4. 
   
5.         //二路归并
   
6.         $arr1 = array(1,3,5);
   
7.         $arr2 = array(2,4,6);
   
8. 
   
9.         //取出一个空数组用于归并空间
   
10.         $arr3 = array();
    
11.         while(count($arr1) && count($arr2)){
    
12.                 //只要$arr1和$arr2里面还有元素，就进行循环
    
13.                 //取出每个数组的第一个元素：进行比较
    
14.                 $arr3[] = $arr1[0]  < $arr2[0] ? array_shift($arr1) : array_shift($arr2);
    
15.         }
    
16. 
    
17.         //合并结果
    
18.         //print_r(array_merge($arr3,$arr1,$arr2));
    
19. 
    
20. 
    
21. 
    
22.         $arr = array(4,7,2,1,5,9,3);
    
23. 
    
24.         //归并排序函数
    
25.         function merge_sort($arr){
    
26.                 //递归出口
    
27.                 $len = count($arr);
    
28.                 if($len <= 1) return $arr;
    
29. 
    
30.                 //拆分
    
31.                 $middle = floor($len / 2);
    
32.                 $left = array_slice($arr,0,$middle);
    
33.                 $right = array_slice($arr,$middle);
    
34. 
    
35.                 //递归点：$left和$right都没有排好序：而且可能是多个元素的数组
    
36.                 $left = merge_sort($left);
    
37.                 $right = merge_sort($right);
    
38. 
    
39.                 //假设左边和右边都已经排好序：二路归并
    
40.                 $m = array();
    
41.                 while(count($left) && count($right)){
    
42.                         //只要$arr1和$arr2里面还有元素，就进行循环
    
43.                         //取出每个数组的第一个元素：进行比较
    
44.                         $m[] = $left[0]  < $right[0] ? array_shift($left) : array_shift($right);
    
45.                 }
    
46.                 //返回结果
    
47.                 return array_merge($m,$left,$right);
    
48.        
    
49.         }
    
50. 
    
51.         print_r(merge_sort($arr));
    
52. ?>

复制代码