首页 > 代码库 > 归并排序、最大子数组
归并排序、最大子数组
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)
不难发现，如果数组元素全为负数，则最大子数组就是最大元素。相应地，也有最小子数组问题。
归并排序、最大子数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。