归并排序的原理就是把一个数组从中间开始分成左右两个数组，对左右两个数组进行排序，最后对排序完的两个部分进行合并，就是一个有序的数组了。
它的思想就是每次把分组分成两个部分，直到不能再继续分下去为止，那么递归就是用来解决这种问题的。
//归并排序
function merge_sort($nums){
if(count($nums)<=1){
return $nums;
}
merge_sort_c($nums,0,count($nums)-1);
return $nums;
}
function merge_sort_c(&$nums,$p,$r)
{
if($p>=$r){
return ;
}
$middle=floor(($p+$r)/2);
merge_sort_c($nums,$p,$middle);
merge_sort_c($nums,$middle+1,$r);
merge($nums,['start'=>$p,'end'=>$middle],['start'=>$middle+1,'end'=>$r]);
}
function merge(&$nums,$array_p,$array_r){
$temp=[];
$p=$array_p['start'];
$r=$array_r['start'];
$k=0;
while($p<=$array_p['end'] && $r<=$array_r['end']){
if($nums[$p]<$nums[$r]){
$temp[$k++]=$nums[$p++];
}else{
$temp[$k++]=$nums[$r++];
}
}
while($p<=$array_p['end']){
$temp[$k++]=$nums[$p++];
}
while($r<=$array_r['end']){
$temp[$k++]=$nums[$r++];
}
for($i=0;$i<$k;$i++){
$nums[$i+$array_p['start']]=$temp[$i];
}
}
$nums=[0,4,5,6,3,2,1,5,7,34,56,93,32,1];
var_dump(merge_sort($nums));exit;归并排序不涉及到相等元素位置的交换，所以是稳定的排序算法。但是我们需要用额外的存储空间存储排序的数组。所以他并不是原地排序，他需要和数组元素大小相等存储空间。空间复杂度是O(n)。
快速排序和归并排序的思想是一样的，但是他们的实现方式是不一样的。快速排序的思想是，如果我们要排序p到r之间的一组数据，我们选择p到r之间的任意一个数作为分区点q，然后遍历p到r之间的数，只要是小于分区点的放在它的左边，大于分区点的放在右边。这样的话，数组p到r就分成了三个部分，小于分区点的，分区点，以及大于分区点的。所以我们可以利用递归的思想，排序下标p到q-1,q+1到r之间的数据，直到区间缩小成1的时候，说明此时整个数组都是有序的。
function quick_sort($nums){
if(count($nums)<=1){
return $nums;
}
quick_sort_c($nums,0,count($nums)-1);
return $nums;
}
function quick_sort_c(&$nums,$p,$r){
if($p>=$r){
return;
}
$provit=is_point($nums,$p,$r);
quick_sort_c($nums,$p,$provit-1);
quick_sort_c($nums,$provit+1,$r);
}
function is_point(&$nums,$p,$r)
{
$provit=$nums[$r];
$i=$p;
for($j=$p;$j<$r;$j++){
///每次把比$provit小的放在[$p-$i-1]中,剩下的放在[$i-$j]都是比$provit大的，
if($nums[$j]<$provit){
$temp=$nums[$i];
$nums[$i]=$nums[$j];
$nums[$j]=$temp;
$i++;
}
}
//最后把$provit放在中间返回
$temp=$nums[$i];
$nums[$i]=$provit;
$nums[$r]=$temp;
return $i;
}
$nums=[4,5,6,3,2,1,7,9,6,0,33];
var_dump(quick_sort($nums));快速排序不是一种稳定的排序，但是他不用设置额外的存储空间，它可以进行原地排序,这是归并排序所没有的。快速排序的特点就是从上至下。咋么说呢，就是每次先解决 大问题，再去解决小问题（先分区，再去处理相同的分区），而归并排序是先处理子问题，然后在合并。
