的std::sort算法(及其同类std::partial_sort和std::nth_element从C++标准库)是在大多数实现的更基本的排序算法复杂和混合合并,如选择排序,插入排序,快速排序,归并排序,或堆排序.
这里和姐妹网站上有很多问题,例如https://codereview.stackexchange.com/,与错误,复杂性以及这些经典排序算法的实现的其他方面有关.大多数提供的实现包括原始循环,使用索引操作和具体类型,并且在正确性和效率方面分析通常是非常重要的.
问:如何使用现代C++实现上述经典排序算法？
<algorithm>auto模板别名,透明比较器和多态lambda.备注:
for比使用运算符的两个函数的组合更长.所以f(g(x));或f(x); g(x);或f(x) + g(x);不生循环,也不是在环路selection_sort和insertion_sort下方.我最近刷了一些基础知识,发现合并排序链表是一个非常好的挑战.如果你有一个很好的实现,那么在这里展示它.
我有一个链表实现,我正在尝试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倍.
对于那些提出要求的人,是的,我需要为这个项目使用我自己的列表类.
这个主题出现在这个主题中,关于对Visual Studio 2015的std :: list :: sort()的更改:
`std :: list <> :: sort()` - 为什么突然切换到自上而下策略？
新版本的std :: list :: sort不需要默认的可构造std :: list,因为它只使用迭代器,并且不创建任何本地列表,因此列表不能是默认值无关紧要建造.先前版本使用本地列表(注意 - 列表的每个实例都涉及动态分配标记节点):
typedef list<_Ty, _Alloc> _Myt;
// ...
const size_t _MAXBINS = 25;
_Myt _Templist, _Binlist[_MAXBINS];
我正在尝试创建一个非默认的可构造列表,使用Visual Studio 2015版本来测试对std :: list :: sort()的更改如何处理.
首先,我尝试了Microsoft C++ 11最小分配器示例.udpate - 为了Jonathan Wakely的回答,我不得不换一行来证明这个问题:
template <class T>
struct Mallocator
{
typedef T value_type;
// Mallocator() noexcept {} // replaced this line from the Microsoft example
Mallocator(T) noexcept {} // no default constructor …在我的应用程序中,我需要对一个相当大的数组进行排序,结果证明这是一个标准的任务,例如std::sort.
位于GUI应用程序中,我想对排序的进度给出某种响应.我的第一个尝试是弄清楚所需比较的大概数量(n*log2(n)for std::sort),然后简单地计算它们在传递给的比较函子中std::sort.这非常有效.
排序算法在单独的线程中执行以保持GUI响应.它使用Qt的信号或一些类似的线程安全机制将其进度传达给GUI.
但是,我也希望排序操作可以中断.也就是说,向用户提供按钮或类似的东西以中止整个操作.目前我只看到两个选项:
pthread_cancel等)考虑到线程取消而不是最后的手段并拒绝重写标准库算法,我抓住了狼的耳朵.
我正在阅读 XOR 链表，我想到了一个问题，在我Is it possible to have a circular XOR linked list?看来，即使我们以某种方式构建了这样一个列表，也不可能在给定列表头节点的情况下遍历它。例如 - 让链表包含 3 个节点：A、B 和 C。
|
v
A ---> B ---> C
A->xor = B ^ C
B->xor = A ^ C
C->xor = A ^ B
由于我们已经给出head了列表，即A在这种情况下，我们将无法向前或向后移动，因为我们必须至少知道B或C中的一个才能移动。由于我们无法遍历它，因此我们也无法构建它。
我的想法正确吗？或者我错过了什么？