1

我对此有疑问；

我有这样的课

class myCLass {
    private:
        string name;
        float value;
    public:
        float getValue();
};

我有超过 1,000,000 个对象，我必须根据其价值对这些项目进行排序。所以我创建了那个指针列表；

list<myClass *> objectList;

然后用超过 1.000.000 个对象填充它。现在您可以说如果您的对象小于 30-40 位，那么矢量是最好的方法，无论如何我创建它是绝对正确的；

bool ec(myClass *s1, myClass *s2) 
{
    return (s1->getValue() < s2->getValue());
}

然后在主函数中；

time = clock();
objectList.sort(ec);    // Sort with STL.
time = clock() - time;
cout << ((float)time)/CLOCKS_PER_SEC << "\t:time to sort" << endl;

而且只需要1.2秒！这对我来说太不可思议了，记住它是最慢的列表容器可能是矢量可以更有效:) 无论如何我的问题是我写了一个插入排序和合并排序算法，如果有人使用我的排序算法，如果他/她想要缩短 100 万个对象需要 3 小时，是的 3 小时 :) 我想知道为什么它比它更多。而且我使用通用算法进行合并和插入，而不是不同的东西，它们计算出真实的结果。例如我的 insertSort() 就是这样；

void sort::insertionSort(list<myClass *> &normalList, list<myClass *> &sortedList){

    list<myClass*>::iterator sortedIterator;

    sortedList.clear();
    iter = normalList.begin(); // iter describing on constructor
    sortedList.push_back(*iter);
    iter++;

    for(; iter != normalList.end(); iter++){

        sortedIterator = (--sortedList.end());

        while( (*iter)->getValue() < (*sortedIterator)->getValue() && sortedIterator!=(--sortedList.begin() ) ){
        sortedIterator--;
        }
        sortedList.insert(++sortedIterator,*iter);
    }
}

我的插入排序（）的基准表；

n=10      => 0      second;
n=100     => 0      second;
n=1.000   => 0      second;
n=10.000  => 0.96   second;
n=20.000  => 4.73   seconds;
n=50.000  => 34.22  seconds;
n=100.000 => 306.62 seconds

我无法控制超过 100.000 :)

那么这是正常的还是我搞错了？

注意：我尝试使用向量进行插入排序，对于 n=100.000，时间是 50 秒，所以尽管 n=100.000 不是 1.000.000，我仍然无法达到 1.29 秒 :)

注 2：这是 mergeSort() 的基准；

n=10      => 0      second;
n=100     => 0      second;
n=1.000   => 0.02      second;
n=10.000  => 0.8   second;
n=20.000  => 3.07   seconds;
n=50.000  => 21.7  seconds;
n=100.000 => 106.73 seconds
4

3 回答 3

2

插入排序比内置算法渐进地慢。虽然插入排序具有O(n^2)内置算法的复杂性，但O(n*log(n))按照标准具有复杂性。因此，与内置排序算法相比，您拥有的元素越多，您的算法就越慢。

实现自己的排序算法几乎不值得，因为内置实现已经非常优化。

于 2013-10-14T15:34:44.500 回答
2

算法理论告诉您，插入排序的复杂度为O(n 2 )，而快速排序的复杂度为O(n log(n))。对于大型数据集，这是一个很大的差异；松散地说，您的算法将慢n / log(n)倍。

当你考虑对数取对数的影响时，这种差异会变得非常大：如果你对宇宙中的粒子数取以 10 为底的对数，答案大约是 87。

于 2013-10-14T15:39:04.287 回答
1

您的版本基本上是将排序列表构造成一个新列表。虽然您只是复制指针，但您仍在为每个节点进行新的分配等。据推测，成员函数 sort 从不创建或删除节点；它通过更改现有节点之间的指针来操作。（当然，不涉及插入排序；它将是纯粹的合并排序。）

于 2013-10-14T15:39:54.953 回答