我一直在尝试进行合并排序和插入排序并比较它们的时间结果。并且从数组输入大小 10 到 10000 合并排序一直比插入排序慢
这是插入排序的代码
vector<int> insertion_sort(vector<int> vec)
{
for(int i = 1 ; i <vec.size();i++)
{
int j = i-1;
while(j>=0 && vec[j+1]<vec[j] )
{
int x = vec[j+1];
vec[j+1] = vec[j];
vec[j--] = x;
}
}
return vec;
}
这是合并排序代码
vector<int> merge(vector<int> left,vector<int> right)
{
int i = 0;
int j = 0;
vector<int> ret(left.size()+right.size());
int it = 0;
for(; i <left.size() && j<right.size();)
{
if(left[i]<right[j])
ret[it++]=(left[i++]);
else if(right[j]<left[i])
ret[it++]=(right[j++]);
else ret[it++]=(left[i++]),ret[it++]=(right[j++]);
}
for(;i<left.size();)
ret[it++]=(left[i++]);
for(;j<right.size();)
ret[it++]=(right[j++]);
return ret;
}
vector<int> merge_sort(vector<int> A,int start,int end)
{
if(start >= end)
{
vector<int> v(1);
v[0]=(A[start]);
return v;
}
int mid = (start+end )/ 2;
vector<int> left = merge_sort(A,start,mid);
vector<int> right = merge_sort(A,mid+1,end);
return merge(left,right);
}
最后这就是我如何调用它们并计算时间
int main()
{
vector<int> rand_vec;
srand(time(0));
for(int i = 0 ; i <SIZE;i++)
{
rand_vec.push_back(rand()%SIZE);
}
int t = clock();
vector<int> merge_sorted = merge_sort(rand_vec,0,rand_vec.size()-1);
puts("");
printf("merge sort time = %d\n",clock() - t );
t = clock();
vector<int> insertion_sorted = insertion_sort(rand_vec);
puts("");
printf("insertion sort time = %d\n",clock() - t );
return 0;
}
我想知道我是否在该代码中做错了什么以使合并排序的时间超过插入排序中使用的时间。
谢谢。