分治算法

• • 使用分治法的题目特征
  • 分治法法的解题步骤
  • 归并排序
  • • 归并排序的主要步骤
    • 归并排序的应用-逆序对问题
  • 快速排序

• 平衡子问题：子问题的规模大致相同，可以把问题划分为k个子问题最好k=2,即分为两个规模相等的子问题。（子问题规模相等的处理效率较高）
• 独立子问题：子问题之间相互独立。这也是区分于动态规划算法的根本特征。

• 分解（divide）：把问题分解为独立的子问题；
• 解决（conquer）：递归解决子问题；
• 合并（combine）：把子问题的结果合并成原问题的解；

• 分解：把初始序列分成长度相等的左右两个序列，然后把每个子序列再分成长度相等的左右两个序列，直到子序列只包含一个数。
• 求解子问题：对子序列排序。
• 合并：归并两个有序的子序列，这是归并排序的主要操作。

归并排序代码

#include
using namespace std;
const int MAX = 100005;
typedef long long ll;
ll a[MAX] = {5,4,4,7,4,3,2,1,1},b[MAX];

void merge(ll l,ll mid,ll r){
    ll i = l,j = mid+1,t = 0;
    while(i<=mid&&j<=r){
        if(a[i]>a[j]){
            b[t++] = a[j++];
        }
        else b[t++] = a[i++];
    }
    while(i<=mid) b[t++] = a[i++];
    while(j<=r) b[t++] = a[j++];
    for(i = 0;i
        a[l+i] = b[i];
    }
}

void mergeSort(ll l,ll r){
    if(l
        ll mid = (l+r)/2;
        mergeSort(l,mid);
        mergeSort(mid+1,r);
        merge(l,mid,r);
    }
}
int main(){
    mergeSort(0,8);
    for(int i = 0;i<8;i++){
        cout< 
归并排序的应用-逆序对问题 
快速排序