c++ - List sort() vs own sort() 时差

Question

我对此有疑问；

我有一个这样的类(class)

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

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

list<myClass *> objectList;

然后用超过 1.000.000 个对象填充它。现在你可以说，如果你的对象小于 30-40 位， vector 是最好的方式，无论如何，这是绝对正确的，然后我创建了它；

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

然后在main函数中；

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

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

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);
    }
}

我的 insertionSort() 的基准表；

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 :)

这是正常现象还是我弄错了？

注意:我尝试使用 vector 进行插入排序并且 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

Answer 1

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

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