快速排序迭代器需求

Question

tl;dr:是否有可能有效地在双链接列表上实现快速排序？我在考虑这件事之前的理解是，不，不是。

有一天，我有机会考虑迭代器对基本排序算法的要求。基本的O(N平方)是相当简单的。

other.

• Insertion

• 排序-2前进迭代器会做得很好，其中一个拖着后面的sort 2双向迭代器就行了。一个用于无序元素，一个用于插入点。

• 选择排序--稍微复杂一点，但前向迭代器可以做到这一点。

快速排序

introsort_loop在std：：排序(在gnu标准库/ hp(1994) /硅图形(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;

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

注意：我尚未尝试实际执行。

Answer 1

tl;dr:是的

正如您所说的，问题是找到pivot元素，它是中间的元素，用随机访问找到这个元素需要O(1)，用双向迭代器查找它需要O(n) (n/2操作，准确地说是n/2操作)。但是，在每个步骤中，您必须创建子容器，左边和右侧分别包含较小和较大的数字。这就是快速排序的主要工作所在，对吗？

现在，在构建子容器(用于递归步骤)时，我的方法是创建一个迭代器h，指向它们各自的前端元素。现在，每当您选择下一个元素到子容器时，每隔一次只需提前h一次。一旦您准备好下降到新的递归步骤，这将使h指向pivot元素。

您只需找到第一个支点，这并不重要，因为O(n log + n/2) = O(n log )。

实际上，这只是一个运行时优化，但对复杂性没有影响，因为无论您是迭代列表一次(将每个值放在相应的子容器中)还是两次迭代(以找到支点，然后将每个值放在相应的子容器中)都是一样的: O(2n) = O(n)。

这只是一个执行时间的问题(而不是复杂性)。

Answer 2

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

Answer 3

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

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

但是，对于链接列表，合并排序算法会带来一个更优雅的实现，它具有同样好的性能(除非您正在处理一些使用快速排序更好的情况)。