相关疑难解决方法(0)

我在接受采访时被问到这个问题.他们都是O(nlogn),但大多数人使用Quicksort而不是Mergesort.这是为什么？

为什么快速排序比合并排序更好？

我有一个链表实现,我正在尝试Mergesort和QuickSort算法.

我不明白为什么std :: list中的排序操作如此之快.查看linux下的std :: list,它似乎也是链表,而不是基于数组的列表.

我尝试的合并排序几乎与Dave Gamble的版本相同: 合并排序链接列表

另外,我想我会尝试一个基于此代码的简单快速排序:http://www.flipcode.com/archives/Quick_Sort_On_Linked_List.shtml

令人惊讶的是,使用std :: list和sort对1000万个随机数进行排序比其他任何一个快10倍.

对于那些提出要求的人,是的,我需要为这个项目使用我自己的列表类.

我试图使用clang编译以下代码但得到以下错误.

我想知道为什么sort从list课堂上使用会有效,但不是std::sort.

#include <list>
#include <iostream>

int main(){
    std::string strings[] = {"hello", "nihao", "byebye", "yo"};
    std::list<std::string> cars(strings, strings+sizeof(strings) / sizeof(char **));

    // cars.sort(std::less<std::string>()); // compiles fine and produce a sorted list

    std::sort(cars.rbegin(), cars.rend(), std::less<std::string>() ); // this one won't compile

    for (std::list<std::string>::iterator it = cars.begin(); it != cars.end(); ++it)
        std::cout << *it << " - ";

    std::cout << std::endl;
    return 0;
}

/usr/include/c++/4.2.1/bits/stl_iterator.h:320:25:错误:二进制表达式的操作数无效('iterator_type'(又名'std :: _ List_iterator>')和'iterator_type'){return __y .base() - __ x.base(); }