算法分析——合并排序和快速排序_采用分治法实现合并排序时间复杂度分析

---

前言

本文用于记录和总结算法学习中关于合并排序和快速排序的内容。合并排序和快速排序运用了分治策略来提高算法的效率，二者是如何体现分治思想，又有何异同呢？

---

一、分治法

在数学上，分治法是这样定义的：

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

For example,给全班同学按照身高进行排队，我们可以依次让每一位同学都与已入列的同学进行比较再入列，这就是最简单的插入排序思想；如果运气好，所有同学的初始站位就是按照身高有序排列的，此时指针老师只需从头至尾地遍历一遍所有数据即可，时间复杂度为。反之，若整个序列散乱排列，那么每个数据都要进行次比较，此时的时间复杂度为，平均时间复杂度为，算法效率非常低！

但是！如果你有幸学习了算法，就不难想到利用分治法的思想，先将同学们分成小组并进行组内排列，再将有序的子模块合并，再次进行组内排序；重复上述步骤，直至这个“模块”中包含了全班所有同学，即回到规模为N的问题中。

简言之，分治法就是将一个复杂问题“向下分解——求解——向上合并”的过程。

二、合并排序

1.基本思想

合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列。

2.复杂度分析

合并排序是一个“对折”的操作过程，对n个元素进行排序，当n=1时终止排序，否则将待排序元素分成大小大致相同的两个子集合，分别对子集合进行排序，最终将排好序的子集合合并成所要求的集合。

总计算时间由合并时间和排序时间两部分组成，其中合并操作总能在时间内完成，所以在最坏情况下所需的时间满足：

则，。

为便于理解，这里给出合并排序的算法描述：

template <class Type>
void MergeSort(Type a[],int n)
{
    Type new Type[n];
    int s=1;
    while(s<n){
        MergePass(a,b,s,n);//合并到数组b
        s+=s;
        MergePass(b,a,s,n);//合并到数组a
        s+=s;
    }
}

三、快速排序

1.基本思想

快速排序基于分治策略的另一个排序算法，其基本思想是在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。

2.复杂度分析

快速排序的运行时间与其划分是否对称有关，最坏情况是划分过程中产生的两个区域分别包含n-1个元素和1个元素，此时的满足：

，

解递归方程可得。

在最好情况下，每次划分所取的pivot都为中值，产生两个大小相同的区域。此时的满足：

，

解得。并且，快速排序平均时间复杂度也是。

以下是快速排序的算法描述：

template <class Type>
void QuickSort(Type a[],int p, int r)
{
    if(p<r){
    int q=Partition(a,p,r);//划分数组
    QuickSort(a,p,q-1);//对左半端排序
    QuickSort(a,q+1,r);//对右半段排序
    }
}

由于划分是快速排序的关键，这里也将其代码附上：

template <class Type>
int Partition(Type a[],int p,int r)
{
    int i=p,j=r+1;
    Type x=a[p];
    while(1){
        while(a[++j]<x);
        while(a[--j]>x);
        if(i>=j) break;
        Swap(a[i],a[j]);
        }
    a[p]=a[j];
    a[j]=x;
    return j;
}

---

总结

合并排序和快速排序的时间复杂度虽然相同，但不难看出合并排序算法更加稳定。一般，我们通过随机生成快速排序的基准元素来降低轴偏移对算法性能的影响。