1

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

我想知道我是否在该代码中做错了什么以使合并排序的时间超过插入排序中使用的时间。

谢谢。

4

4 回答 4

3

通过引用而不是通过值传递向量会产生巨大的差异。在我的机器上，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)
于 2013-10-12T01:49:04.460 回答
1

总结到目前为止提供的答案：
- 使用引用（或指针）来避免复制向量：
-reserve在您事先知道大小时使用，然后再使用数千个push_back（这样您就不需要在超过容量时动态重新分配）
- 您可以const vector<int>& merge_sorted = ...在返回矢量时避免复制

于 2013-10-12T01:31:01.640 回答
0

除了关于引用的 mrip 答案外，请记住：

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

于 2013-10-12T15:09:14.973 回答
0

合并排序不一定比插入排序慢。插入排序对“n”个项目进行排序所花费的时间与 n 平方 (n n) 成正比，而合并排序所花费的时间与 n 以 n 为底的 2 的对数 (n lgn) 成正比，因此插入排序比合并排序快在某些代码中，而在其他代码中合并排序

于 2016-11-29T07:24:09.213 回答