8

tl; dr：是否可以有效地在双向链表上实现快速排序？在考虑之前我的理解是，不，不是。

前几天我有机会考虑基本排序算法的迭代器要求。基本的 O(N²) 相当简单。

  • 冒泡排序 - 2 个前向迭代器会做得很好，一个接一个拖着。
  • 插入排序 - 2 个双向迭代器就可以了。一个用于乱序元素，一个用于插入点。
  • 选择排序 - 有点棘手，但前向迭代器可以解决问题。

快速排序

std::sort 中的 introsort_loop（如在 gnu 标准库/hp(1994)/silicon graphics(1996) 中）要求它是 random_access。

__introsort_loop(_RandomAccessIterator __first,
         _RandomAccessIterator __last,
         _Size __depth_limit, _Compare __comp)

正如我所期待的那样。

现在经过仔细检查，我找不到需要快速排序的真正原因。唯一明确需要 random_access_iterators 的是std::__median需要计算中间元素的调用。常规的香草快速排序不计算中位数。

分区包括一个检查

 if (!(__first < __last))
    return __first;

不是真正有用的双向检查。然而，人们应该能够用一个简单的条件来替换前一个分区旅行（从左到右/从右到左）中的检查

if ( __first == __last ) this_partitioning_is_done = true;

是否可以仅使用双向迭代器相当有效地实现快速排序？递归深度仍然可以被保护。

注意。我还没有尝试过实际的实现。

4

3 回答 3

2

您需要随机访问迭代器，因为您通常希望从列表中间选择枢轴元素。如果您选择第一个或最后一个元素作为枢轴，双向迭代器就足够了，但是对于预排序列表，快速排序会退化为 O(n^2)。

于 2011-09-28T16:51:20.013 回答
1

tl;博士：是的

正如您所说，问题是找到枢轴元素，即中间的元素，通过随机访问找到它需要 O(1)，使用双向迭代器找到它需要 O(n)（n/2 次操作，即精确的）。但是，在每个步骤中，您必须创建子容器，左侧和右侧分别包含较小和较大的数字。这就是快速排序的主要工作发生的地方，对吧？

现在，在构建子容器（用于递归步骤）时，我的方法是创建一个h指向它们各自前端元素的迭代器。现在，每当您选择下一个元素进入子容器时，只需h每秒钟前进一次。一旦您准备好下降到新的递归步骤，这将h指向枢轴元素。

你只需要找到第一个无关紧要的支点，因为 O(n log n + n/2) = O(n log n)。

实际上，这只是一个运行时优化，但对复杂性没有影响，因为无论您迭代列表一次（将每个值放入相应的子容器中）还是两次（找到枢轴然后将每个值放入相应的子容器）都是一样的：O(2n) = O(n)。
这只是执行时间（而不是复杂性）的问题。

于 2011-09-28T17:06:22.000 回答
1

在双向链表上实施快速排序策略绝对没有问题。（我认为它也可以很容易地适应单链表）。传统快速排序算法中唯一依赖于随机访问要求的地方是设置阶段，它使用“棘手”的东西来选择枢轴元素。实际上，所有这些“技巧”只不过是可以用几乎同样有效的顺序方法代替的启发式方法。

我之前已经为链表实现了快速排序。它没有什么特别之处，您只需要密切注意适当的元素重新链接。正如您可能理解的那样，列表排序算法的大部分价值来自您可以通过重新链接来重新排序元素，而不是显式的值交换。它不仅可以更快，而且（而且通常 - 更重要的是）保留了可能附加到列表元素的外部引用的值有效性。

PS 但是，我想说的是，对于链表，合并排序算法会产生一个更加优雅的实现，它具有同样好的性能（除非您正在处理一些特别是使用快速排序表现更好的情况）。

于 2011-09-28T17:16:09.827 回答