算法1：归并排序算法

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，最后把所有的求解合并起来)。

具体的实现有三个步骤：

1. 分解：将当前区间一分为二，即求分裂点 mid = (low + high)/2;
2. 求解：递归地对两个子区间a[low…mid] 和 a[mid+1…high]进行归并排序。递归的终结条件是子区间长度为1。
3. 合并：将已排序的两个子区间a[low…mid]和 a[mid+1…high]归并为一个有序的区间a[low…high]。

把一个8个元素的数组分割成到只有一个元素的数组，需要分割3次（即 l o g 2 8 {log_2{8}} log2​8）

n个元素的数组需要分割 l o g 2 n {log_2{n}} log2​n ,所以时间复杂度为 l o g n {log{n}} logn

合并时每次都要把两个有序的子数组汇总成一个更大的有序数组，所需的时间复杂度为O(n)。所以总的时间复杂度为O(n l o g n {log{n}} logn )

算法实现
方式1:递归——自顶向下

递归过程是将待排序数组一分为二，直至排序数组就剩下一个元素为止，然后不断的合并两个排好序的数组

合并过程如下（这里以第2趟归并为例）：

代码如下

 
逻辑说明：mergeSort()把数组递归分割，直到每个数组只有一个数组为止，接着就开始合并，合并的逻辑是分割后的左边数组和右边数组不断遍历，比较两个元素的值，小的值就存入临时数组，并继续遍历，直到有一个遍历结束
 
方式1:非递归——自底向上
 
非递归过程是将待排序数组看成n个长度为1的子序列，数组中的相邻元素两两配对，将他它们排序后，构成n/2组长度为2的排序好的子数组段，然后再将他们排序成长度为4的子数组段，如此继续下去，直至整个数组排好序。
 

 代码如下
 
 $len - 1) { // 如果第二个序列个数不足size个
                //调整 right 为最后一个元素的下标即可
                $right = $len - 1;
            }
            // 调用归并函数，进行分割的序列的分段排序
            merge($arr, $left, $mid, $right);
            $left = $right + 1;
        }
        $size *= 2; // 范围扩大一倍
    }
}
 
// 将两个有序数组合并成一个有序数组
function merge(&$arr, $left, $mid, $right) {
    $i = $left;     // 左数组的下标
    $j = $mid + 1;  // 右数组的下标
    $temp = array();// 临时合并数组
    // 扫描第一段和第二段序列，直到有一个扫描结束
    while ($i <= $mid && $j <= $right) {
        // 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
        if ($arr[$i] < $arr[$j]) {
            $temp[] = $arr[$i];
            $i++;
        } else {
            $temp[] = $arr[$j];
            $j++;
        }
    }
    // 比完之后，假如左数组仍有剩余，则直接全部复制到 temp 数组
    while ($i <= $mid) {
        $temp[] = $arr[$i];
        $i++;
    }
    // 比完之后，假如右数组仍有剩余，则直接全部复制到 temp 数组
    while ($j <= $right) {
        $temp[] = $arr[$j];
        $j++;
    }
    // 将合并序列复制到原始序列中
    
    for ($i = $left, $k = 0; $i <= $right; $i++, $k++) {
        $arr[$i] = $temp[$k];
    }
}
 
// 测试
$arr = [9,4,8,6,5,7,3];
mSort($arr);
print_r($arr);
 
不管递归还是非递归，其合并的逻辑都是一样的。
 
效率分析
 1、时间复杂度：O(n
    
     
      
       
        l
       
       
        o
       
       
        g
       
       
        n
       
      
      
       {log{n}}
      
     
    logn)
 最好情况、最坏情况和平均时间复杂度均为O(n
    
     
      
       
        l
       
       
        o
       
       
        g
       
       
        n
       
      
      
       {log{n}}
      
     
    logn);
 2、空间复杂度：O(n)
 算法处理过程中，需要一个大小为 n 的临时存储空间保存合并序列，所以空间复杂度为O(n)。
 3、稳定性：稳定
 在归并排序中，相等的元素的顺序不会改变，所以它是稳定排序。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5686269.html