归并排序、最大子数组

1.归并排序

分治模式：

（1）分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。

（2）解决子问题，递归求解子问题。子问题规模足够小时，直接求解。

（3）合并子问题的解，得到原问题的解。

归并排序完全遵循分治模式。

（1）分解待排序的n个元素列成各具n/2个元素的两个子序列。

（2）使用归并排序递归地排序两个子序列。

（3）合并两个已排序的子序列，产生已排序的答案。

时间复杂度：T(n)=O(n*lgn)

代码：

#include<iostream>
#include<vector>
using namespace std;

vector<int> merge(vector<int> vec1, vector<int> vec2)
{
    vector<int> vec;

    auto it1 = vec1.begin();
    auto it2 = vec2.begin();

    while (it1 != vec1.end() && it2 != vec2.end())
    {
        if (*it1<*it2)
        {
            vec.push_back(*it1);
            ++it1;
        }
        else
        {
            vec.push_back(*it2);
            ++it2;
        }
    }

    while (it1 != vec1.end())
    {
        vec.push_back(*it1);
        ++it1;
    }

    while (it2 != vec2.end())
    {
        vec.push_back(*it2);
        ++it2;
    }

    return vec;
}

void merge_sort(vector<int> &vec)
{
    if (vec.size()>1)//
    {
        vector<int> vec1;
        for (auto it = vec.begin(); it !=vec.begin() + (vec.end() - vec.begin()) / 2; ++it)
        {
            vec1.push_back(*it);
        }
        merge_sort(vec1);//

        vector<int> vec2;
        for (auto it = vec.begin()+(vec.end() - vec.begin()) / 2 ; it != vec.end(); ++it)
        {
            vec2.push_back(*it);
        }
        merge_sort(vec2);//

        vector<int> temp = merge(vec1, vec2);//

        vec = temp;////保存已排序的部分元素 
    }
}

int main()
{
    vector<int> vec = { 2, 3, 2, 5, 6, 1, -1, 3, 14, 12 };
    merge_sort(vec);
    for (auto c : vec)
        cout << c << ",";

    cout << endl;

    system("pause");
    return 0;
}

2.最大子数组问题

在含有负数（如果数组元素全部为正数，那最大子数组就是整个数组）的数组中找出元素之和最大的子数组。

使用分治策略的求解方法：

设有A[low...high],mid=(low+high)/2,则最大子数组A[i...j]：

（1）完全在A[low...mid]中,low<=i<=j<=mid.//子问题

（2）完全在A[mid+1...high]中，mid<i<=j<=high.//子问题

（3）跨越了中点，low<=i<=mid<j<=high.//新问题

在三种情况中选取和最大者。

伪代码：

array<int,3> find_max_subarray(ivec,int low,int high)
{
    if(low==high)
        return {low,high,ivec[low]};//base case:only one element
    else{
        int mid=(low+high)/2;
        
        left=find_max_subarray(ivec,low,mid);
        right=find_max_subarray(ivec,mid+1,high);
        cross=find_max_crossing_subarray(ivec,low,mid ,high);
        
        if(left[2]>=right[2]&&left[2]>=cross[2])
            return left;
        else if(right[2]>=left[2]&&right[2]>=cross[2])
            return right;
        else
            return cross;
}

array<int,3> find_max_crossing_subarray(ivec,int low,int mid,int high)
{
    int left_sum=MIN;
    int right_sum=MIN;
    int sum=0;
    int max_left=mid,max_right=mid;
    
    for(int i=mid;i>=low;i--)
    {
        sum+=ivec[i];
        if(sum>left_sum)
        {
            left_sum=sum;
            max_left=i;
        }
    }
    
    sum=0;
    for(int j=mid+1;j<=high;j++)
    {
        sum+=ivec[j];
        if(sum>right_sum)
        {
            right_sum=sum;
            max_right=j;
        }
    }
    
    return {max_left,max_right,left_sum+right_sum};//最左下标、最右下标、元素之和
}

时间复杂度：T(n)=O(n*lgn)

不难发现，如果数组元素全为负数，则最大子数组就是最大元素。相应地，也有最小子数组问题。

如果修改最大子数组定义，允许最大子数组为空，其和为0。在find_max_crossing_subarray函数中设置left-max,right-max初始值设为-1，left-sum,right-sum初始值设为0。另外find_max_subarray函数中，当low==high时

 if(low==high){
    if(ivec[low]>0){
        return {low,high,ivec[low]};//base case:only one element
    }
    else{
        return {-1,-1,0}
    }
}

更多讨论。