10

我有一个链表实现，我正在试验 Mergesort 和 QuickSort 算法。

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

我在这里尝试的合并排序与 Dave Gamble 的版本几乎相同： Merge Sort a Linked List

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

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

对于那些询问的人，是的，我需要为这个项目使用我自己的列表类。

4

1 回答 1

14

我一直在研究list::sort（源代码）的有趣 GLibC 实现，它似乎没有实现传统的合并排序算法（至少我以前从未见过）。

基本上它的作用是：

  1. 创建一系列桶（总共 64 个）。
  2. 删除要排序的列表的第一个元素，并将其与第一个 ( i=0th) 桶合并。
  3. 如果在合并之前i第 th 桶不为空，则将i第 th 桶与第i+1th 桶合并。
  4. 重复步骤 3，直到我们与一个空桶合并。
  5. 重复步骤 2 和 3，直到要排序的列表为空。
  6. 从最小到最大将所有剩余的非空桶合并在一起。

小提示：将存储桶X与存储桶合并Y将从存储桶中删除所有元素X并将它们添加到存储桶Y中，同时保持所有内容排序。另请注意，存储桶中的元素数为0或2^i。

现在为什么这比传统的合并排序更快？好吧，我不能肯定地说，但我想到了一些事情：

  • 它从不遍历列表以找到中点，这也使算法对缓存更加友好。
  • 由于较早的存储桶较小且使用更频繁，因此merge对缓存的调用频率较低。
  • 编译器能够更好地优化此实现。需要比较生成的程序集才能确定这一点。

我很确定实现这个算法的人已经对其进行了彻底的测试，所以如果你想要一个明确的答案，你可能不得不在 GCC 邮件列表上询问。

于 2011-07-18T06:07:10.173 回答