【排序】归并排序

落日映苍穹つ 2022-06-18 10:45 221阅读 0赞

归并排序的基本思想是：将两个（或以上）的有序表组成新的有序表。

更实际的意义：可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列,首先做两两归并，得到n / 2个长度为 2 的子序列 ；再做两两归并，…，如此重复，直到最后得到一个长度为 n 的有序序列。

关键字序列T=（21，25，49，25\*，93，62，72，08，37，16，54），请给出归并排序的具体实现过程。

![图示][SouthEast]

![图示][SouthEast 1]

![图示][SouthEast 2]

PHP的实现

<?php
    //归并操作
    function Merge(array &$arr,$start,$mid,$end){
        $i = $start;
        $j=$mid + 1;
        $k = $start;
        $temparr = array();
    
        while($i!=$mid+1 && $j!=$end+1)
        {
            if($arr[$i] >= $arr[$j]){
                $temparr[$k++] = $arr[$j++];
            }
            else{
                $temparr[$k++] = $arr[$i++];
            }
        }
    
        //将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
        while($i != $mid+1){
            $temparr[$k++] = $arr[$i++];
        }
        //将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
        while($j != $end+1){
            $temparr[$k++] = $arr[$j++];
        }
        for($i=$start; $i<=$end; $i++){
            $arr[$i] = $temparr[$i];
        }
    }
    function MSort(array &$arr,$start,$end){
        //当子序列长度为1时，$start == $end，不用再分组
        if($start < $end){
            $mid = floor(($start + $end) / 2);	//将 $arr 平分为 $arr[$start - $mid] 和 $arr[$mid+1 - $end]
            MSort($arr,$start,$mid);			//将 $arr[$start - $mid] 归并为有序的$arr[$start - $mid]
            MSort($arr,$mid + 1,$end);			//将 $arr[$mid+1 - $end] 归并为有序的 $arr[$mid+1 - $end]
            Merge($arr,$start,$mid,$end);       //将$arr[$start - $mid]部分和$arr[$mid+1 - $end]部分合并起来成为有序的$arr[$start - $end]
        }
    }
    
    //归并算法总函数
    function MergeSort(array &$arr){
        $start = 0;
        $end = count($arr) - 1;
        MSort($arr,$start,$end);
    }
    
    $arr = array(2,3,1,5,4);
    MergeSort($arr);
    var_dump($arr);

运行结果：

array(5) \{ \[0\]=> int(1) \[1\]=> int(2) \[2\]=> int(3) \[3\]=> int(4) \[4\]=> int(5) \}

# 归并排序算法分析： #

![图示][SouthEast 3]

[SouthEast]: /images/20220618/4b1a24a47c4740a38626acab0947e71b.png
[SouthEast 1]: /images/20220618/3f3f31f87146411eb74c7136749fe5aa.png
[SouthEast 2]: /images/20220618/2997fdf32d0e40f19c95a920a8c3a50a.png
[SouthEast 3]: /images/20220618/095612740cb1460d9135b873de60692e.png