为什么我的合并排序代码比插入排序慢

Question

我一直在尝试进行合并排序和插入排序，并比较两者的时间结果。从数组输入大小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;
}

我想知道我是否在代码中做错了什么，使合并排序的时间比插入排序所用的时间更长。

谢谢。

Answer 1

总结迄今所提供的答复：

• 使用引用(或指针)避免复制向量：
• 在使用数千个reserve之前，事先知道大小时使用push_back (这样就不需要在超出容量时动态地重新分配)。
• 您可以在返回向量时执行const vector<int>& merge_sorted = ...以避免复制。

Answer 2

通过参考传递向量而不是通过值传递会产生巨大的差异。在我的机器上用SIZE=50000编译，用-O3编译，之前：

merge sort time = 5730000

insertion sort time = 1470000

之后：

merge sort time = 10000

insertion sort time = 1470000

我只换了两行：

vector<int> merge(const vector<int> &left,const vector<int> &right)
vector<int> merge_sort(const vector<int> &A,int start,int end) 

Answer 3

除了关于推荐信的mrip回答外，请记住：

“插入排序是排序非常小的数组的最快算法之一，甚至比快速排序还要快。最好的情况输入是已经排序的数组。在这种情况下，插入排序具有线性运行时间。最简单的最坏情况输入是按反向顺序排序的数组。”