Tools

算法（四）归并排序、快速排序

阅读：530 发布：2018-11-21 作者：lypeng

![](/uploads/lypeng/2018112102.jpg)

![](/uploads/lypeng/2018112101.jpg)

## 上代码

```php
<?php
// 归并排序
// 一半一半的分下去，最后比较两个元素的大小，在合并
// array_chunk(array,size,preserve_key); 函数把数组分割为新的数组块。
// 其中每个数组的单元数目由 size 参数决定。
// 最后一个数组的单元数目可能会少几个。
// 可选参数 preserve_key 是一个布尔值，它指定新数组的元素是否有和原数组相同的键（用于关联数组），还是从 0 开始的新数字键（用于索引数组）。默认是分配新的键。
// from: https://www.jb51.net/article/132134.htm
function merge_sort($arr){
    $length=count($arr);
    if($length<=1){
        return $arr;
    }
    //分解数组，递归排序
    $half=ceil($length/2);
    $arr2=array_chunk($arr,$half);
    $left=merge_sort($arr2[0]);
    $right=merge_sort($arr2[1]);
    while(count($left)&&count($right)){
        if($left[0]<$right[0]){
            $reg[]=array_shift($left);
        }else{
            $reg[]=array_shift($right);
        }
    }
    return array_merge($reg,$left,$right);
}

// 快速排序
// 从队尾取出一个元素，剩下的跟它比较，大于的放右边，小于的放左边，不断进行此操作，最后合并
function quick_sort($arr){
    $length=count($arr);
    if($length<=1){
        return $arr;
    }
    $end = array_pop($arr);
    $left = $right = array();
    foreach ($arr as $k => $v) {
        if($v <= $end){
            $left[]=$v;
        }else{
            $right[]=$v;
        }
    }
    $l = quick_sort($left);
    $r = quick_sort($right);
    return array_merge($l,array($end),$r);
}
$arr = array(5,6,8,9,12,35,4);
var_dump(quick_sort($arr));

?>
```

------本文结束感谢阅读------

上一篇：算法（三）冒泡排序、插入排序、选择排序、归并排序、快速排序

下一篇：没有了