排序——快排与归并排

快排、归并排：

归并排：

归并排序和快速排序都用到了分治思想，非常巧妙,空间复杂度O(nlogn)，不是原地排序

分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧

基本逻辑：如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
merge_sort_c([9, 11, 8,13] 0,3); 升序
//递归的最后一层，实际上是两个数的比较，倒数第二层开始，第一个数组的第一个和第二数组的第一个比较（有点 类似双指针法）
参考动图：https://www.cnblogs.com/lxhyty/p/11231927.html
function merge_sort_c(&$arr, $start, $end)
{
    if($start >= $end){
        return;
    }
    $middle = (floor)(($start +$end)/2);// 1   0            分解
    merge_sort_c($arr, $start, $middle);//arr,0,1    arr,0,0
    merge_sort_c($arr, $middle+1, $end);//arr,2,2 arr,1,1
 
    merger($arr, $start, $middle, $end);//arr,0,1,3   arr,0,0,1    排序、合并数组
}
 
function merger(&$arr, $start, $middle, $end) //arr,0,0,1
{
    $i = $start;
    $j = $middle+1;
    $arrTemp =[];
    while($i<=$middle && $j<=$end){
       if($arr[$i] <= $arr[$j]){
           $arrTemp[] =$arr[$i];
           $i++;
       }else{
           $arrTemp[] =$arr[$j];
           $j++;
       }
    }
    while($i <= $middle){
        $arrTemp[] =$arr[$i];
        $i++;
    }
    while($j<=$end){
        $arrTemp[] =$arr[$j];
        $j++;
    }
 
    $i = $start;
    foreach ($arrTemp as $key=>$val){
        $arr[$i]= $val;
        $i++;
    }
    return ;
}


快排：

快排核心思想就是分治和分区

基本逻辑：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点），分三部分：将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间，递归终止条件——区间缩小到1，即剩余1个元素。

array_merge()时间复杂度为O(n)线性阶，而快排的时间复杂度是O(nlogn)线性对数阶，极端情况下([1,2,3,4,5,6,7,8,9]，已经有序)退化为O(n2)，快排是一种原地、不稳定的排序算法，递归来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
$a = [9, 11, 8,13];

function quick_sort($a) //8    【9】    11,13
{
    if (count($a) <= 1) {
        return $a;
    }
    $middle = $a[0]; // 中间值  
    $left = array(); // 接收小于中间值
    $right = array();// 接收大于中间值

    for ($i=1; $i < count($a); $i++) {  // 循环比较
        if ($middle < $a[$i]) {
            $right[] = $a[$i];
        } else {
            $left[] = $a[$i];
        }
    }

    $left = quick_sort($left); 
    $right = quick_sort($right);
    
    return array_merge($left, array($middle), $right);  
}
print_r(quick_sort($a));

快排与归并排的比较：

归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法，这也使它存在致命的缺点，即归并排序不是原地排序算法，空间复杂度比较高，是 O(n)。正因为此，它也没有快排应用广泛。

快速排序算法虽然最坏情况下的时间复杂度是 O(n2)，但是平均情况下时间复杂度都是 O(nlogn)。不仅如此，快速排序算法时间复杂度退化到 O(n2) 的概率非常小，我们可以通过合理地选择 pivot 来避免这种情况。

以上学于极客时间，做的笔记