|
#2
雪影辰风2020-04-05 17:33
STL容器我不是很会用，所以跟你讲讲原理吧……
分治排序的原理就是，把一个大问题不断分解成小问题 这里你的算法应该是二分（也就是每次分解成两个小问题实现） 比如说我有如下几个数需要排序：1,3,5,7,9,2,4,6,8 然后我们进行问题分解，求出数集的中间元素也就是下标最靠中的那个（偶数的话会有两个结果，取左取右都可以），也就是9，记录下标是4（注意下标从0开始），则左边有一个区间下标0-3，右边5-8（这里大致讲个原理，实际我也不知道，因为你的代码用了STL，我看不懂，不好意思  ）然后进行两次递归第一次：1,3,5,7 求出数集的中间元素也就是下标最靠中的那个，也就是3（根据习惯取值，这里取左值），记录下标是1（注意下标从0开始），则左边有一个区间下标0-0，右边2-3 然后再次递归左区间，和右区间，如此循环往复 第二次：2,4,6,8 求出数集的中间元素也就是下标最靠中的那个，也就是4（根据习惯取值，这里取左值），记录下标是6（注意下标从0开始），则左边有一个区间下标5-5，右边7-8 然后再次递归左区间，和右区间，如此循环往复 【大致就是这个原理，肯可能有点绕，看不懂我再想办法吧……】 |
程序代码：#include <iostream>
#include<vector>
#include<algorithm>
#include <iterator>
void mergesort(std::vector<int>&myarray,size_t l,size_t r);
void msort(std::vector<int>&myarray,size_t l,size_t m,size_t r)
{
size_t n1=m-l+1;
size_t n2=r-m;
std::vector<int>L(n1);
std::vector<int>R(n2);
for(size_t i=0;i<n1;++i)
{
L[i]=myarray[i];//std::cout<<L[i]<<std::endl;
}
for(size_t i=1;i<n2;++i)
{
R[i]=myarray[i+m];//std::cout<<R[i]<<std::endl;
}
/**< 小黄和大绿，小黄的第一个元素是否小于大绿的第一个元素 ，小于的话就把该元素放在总桶的第一个，
比较小黄的第二个和大黄的第一个比较*/
for(size_t k=l,i=0,j=1;k<r;++k)
{
if(R[j]<L[i])
{
myarray[k]=R[j];
j+=1;
}
else
{myarray[k]=L[i];
i+=1;}
}
}
void mergesort(std::vector<int>&myarray,size_t l,size_t r)
{
if(l>r)
{ size_t m=(l+r)/2;
mergesort(myarray,l,m);//递归这是跟着算法导论的伪代码敲的，一层递归我还是能理解的，双层递归现在理解起来有点难
mergesort(myarray,m+1,r);
msort(myarray,l,m,r);}
}
int main()
{
std::vector<int>myarray{1,3,5,7,9,2,4,6,8};
// msort(myarray,0,(myarray.size()/2),myarray.size());
mergesort(myarray,0,myarray.size());
for(std::vector<int>::size_type i=0;i<myarray.size();++i)
{
std::cout<<myarray.at(i)<<std::endl;
}
}
确实是我归并那和执行条件那错了，大部分是根据算法书上的伪代码进行分析的，细节上不到位，感谢2楼和7楼的补充，