5.归并排序
5.1归并排序的思想和复杂度
归并排序思想
归并排序主要是分治法的思想，有自顶向下和自底向上的归并排序。
归并排序通过递归将一个数组一分为二，然后将两个数组分别进行排序，对两个数组又进行划分，划分成四个数组，依次类推，直到将整个数组分解完毕。每次将数组进行二分后，需要将两个排序完毕的数组进行归并。例如，将8个数组归并成4个数组，4个数组归并成2个数组，2个数组归并成1个数组。最后就完成了整个数组的排序.
时间和空间复杂度
时间复杂度如表所示
| 算法 | 平均情况 | 最好情况 | 最差情况 |
|---|---|---|---|
| 冒泡 | O(NlogN) | O(NlogN) | O(NlogN) |
空间复杂度：O(N)
5.2归并排序的操作
假设有这样一个数组vec：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 数组 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
归并方法
先上代码
void merge(vector<int> &aux,vector<int> &vec,int lo,int mid,int hi)
{
int i=lo,j=mid+1;
for(int k=lo;k<=hi;k++)
{
aux[k]=vec[k];
}
for(int k=lo;k<=hi;k++)
{
if(i>mid) vec[k]=aux[j++];
else if(j>hi) vec[k]=aux[i++];
else if(aux[i]>aux[j]) vec[k]=aux[j++];
else vec[k]-aux[i++]; //if(aux[i]<=aux[j])
}
show(vec);
}
归并排序中最关键的一步就是将两个子数组进行归并。上面的merge函数中，需要提供一个辅助数组aux，原数组vec，以及需要归并的索引lo，mid，hi。其中，lomid是前半部分子数组，mid+1hi是后半部分子数组。归并完成后就将原数组vec的vec[lo]~vec[hi]完成了排序。
自顶向下的归并排序
void sort_ub(vector<int> &vec)
{
vector<int> aux(vec.size());
sort_ub(aux,vec,0,vec.size()-1);
}
void sort_ub(vector<int> &aux,vector<int> &vec,int lo,int hi)
{
if(hi<=lo)return;
int mid = lo+(hi-lo)/2;
sort_ub(aux,vec,lo,mid);
sort_ub(aux,vec,mid+1,hi);
merge(aux,vec,lo,mid,hi);
}
递归分治
- 每次sort_ub找到lo和hi中间的mid，
- 将前半部分vec[lo]~vec[mid]排序
- 将后半部分vec[mid]~vec[hi]排序
- 将vec[lo]~vec[hi]归并
自底向上的归并排序
sort_bu(vector<int> &vec)
{
vector<int> aux(vec.size());
sort_bu(aux,vec);
}
sort_bu(vector<int> &aux,vector<int> &vec)
{
int number=vec.size();
for(int sz=1;sz<number;sz=sz+sz)//sz是子数组的大小
for(int lo=0;lo<number-sz;lo=lo+sz+sz)
//lo是子数组的最低位索引，首先需要确定lo
//确定lo就可以根据lo和sz确定mid，确定mid就可以根据mid和sz确定hi，但边界条件还有个number-1,用来处理数组长度不为2次幂的情况
{
merge(aux,vec,lo,lo+(sz-1),lo+(sz-1)+sz<number-1?lo+(sz-1)+sz:number-1);
}
}
自底向上：
将整个数组进行两两划分，划分到子数组的长度为sz=1。
然后长度为sz的数组两两进行归并
sz=1时，整个数组有N=vec.size()个子数组
sz=2时，整个数组有N/2个子数组
sz=4时，整个数组有N/4个子数组
..................
sz=N时，整个数组有N/N=1个数组，这个时候就归并完毕了边界条件：如果数组vec的长度不为2的幂，那么最后一次归并可能不是两两对称的，因此需要加一个边界条件lo+(sz-1)+sz<number-1?lo+(sz-1)+sz:number-1，目的就是为了将两个不对称的数组进行归并。
自底向上的归并过程中，前一次操作中已经完成排序，每一次的操作就是将分散的子数组合并成一个个更长的数组，最后完成整个数组的排序
OK, 可以上代码了。
5.3 C++代码
#include <iostream>
#include <vector>
using namespace std;
class Sort
{
public:
void sort_ub(vector<int> &vec)
{
vector<int> aux(vec.size());
sort_ub(aux,vec,0,vec.size()-1);
}
void sort_ub(vector<int> &aux,vector<int> &vec,int lo,int hi)
{
if(hi<=lo)return;
int mid = lo+(hi-lo)/2;
sort_ub(aux,vec,lo,mid);
sort_ub(aux,vec,mid+1,hi);
merge(aux,vec,lo,mid,hi);
}
sort_bu(vector<int> &vec)
{
vector<int> aux(vec.size());
sort_bu(aux,vec);
}
sort_bu(vector<int> &aux,vector<int> &vec)
{
int number=vec.size();
for(int sz=1;sz<number;sz=sz+sz)//sz是子数组的大小
for(int lo=0;lo<number-sz;lo=lo+sz+sz)
//lo是子数组的最低位索引，首先需要确定lo
//确定lo就可以根据lo和sz确定mid，确定mid就可以根据mid和sz确定hi，但边界条件还有个number-1,用来处理数组长度不为2次幂的情况
{
merge(aux,vec,lo,lo+(sz-1),lo+(sz-1)+sz<number-1?lo+(sz-1)+sz:number-1);
}
}
void merge(vector<int> &aux,vector<int> &vec,int lo,int mid,int hi)
{
int i=lo,j=mid+1;
for(int k=lo;k<=hi;k++)
{
aux[k]=vec[k];
}
for(int k=lo;k<=hi;k++)
{
if(i>mid) vec[k]=aux[j++];
else if(j>hi) vec[k]=aux[i++];
else if(aux[i]>aux[j]) vec[k]=aux[j++];
else vec[k]-aux[i++]; //if(aux[i]<=aux[j])
}
show(vec);
}
void show(vector<int> &vec)
{
for(int i=0;i<vec.size();i++)
{
cout << vec[i] << " ";
}
cout << endl;
}
vector<int> init()
{
vector<int> vec;
// int arr[10]={4,3,5,2,1,9,8,6,0,7};
int arr[10]={9,8,7,6,5,4,3,2,1,0};
vec.insert(vec.begin(),arr,arr+10);
cout <<"ori:"<<endl;
show(vec);
cout <<"-------------------"<<endl;
return vec;
}
bool checkorder(vector<int> &vec)
{
for(int i=0;i<vec.size()-1;i++)
{
if(vec[i]>vec[i+1])return false;
}
return true;
}
private:
void exch(vector<int> &vec,int a,int b)
{
int tmp;
tmp=vec[a];
vec[a]=vec[b];
vec[b]=tmp;
}
};
int main()
{
Sort sortob;
vector<int> mvec=sortob.init();
// sortob.sort_ub(mvec);
sortob.sort_bu(mvec);
cout <<"------result-------"<<endl;
if(sortob.checkorder(mvec))
sortob.show(mvec);
else
{ cout << sortob.checkorder(mvec);
}
return 0;
}
输出结果：
image.png
