最近在学数据结构和算法,想简单模拟一下向量的归并排序
#include<iostream>
using namespace std;
class vector
{
int* num;
public:
vector(int *k)
{
num=k;
}
void mergesort(int,int);
void merge(int,int,int);
void display()
{
for(int i=0;i<10;i++)
cout<<num[i]<<endl;
}
};
void vector::mergesort(int low,int high)
{
if(high-low<2)return;
int mi=(low+high)/2;
mergesort(low,mi);
mergesort(mi,high);
merge(low,mi,high);
}
void vector::merge(int low,int mi,int high)
{
int* A=num+low;
int lenb=mi-low;
int *B=new int[lenb];
for(int i=0;i<lenb;i++)B[i]=A[i];
int lenc=high-mi;
int *C=num+mi;
for(int i=0,j=0,k=0;(j<lenb)||(k<lenc);)
{
if((j<lenb)&&(lenc<=k||(B[j]<=C[k])))A[i++]=B[j++];
if((k<lenc)&&(lenb<=j||(C[k]<B[j])))A[i++]=C[k++];
}
delete[]B;
}
int main()
{
int *k;
for(int i=0;i<10;i++)
cin>>k[i];
cout<<"一开始"<<endl;
for(int i=0;i<10;i++)
cout<<" "<<k[i];
cout<<endl;
vector v(k);
v.mergesort(0,10);
v.display();