快速排序迭代器要求

Question

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

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

快速排序

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;

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

NB.我还没有尝试过实际的实现.

Answer 1

长话短说：是的

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

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

你只需要找到第一个主元，这实际上并不重要，因为 O(n log n + n/2) = O(n log n)。

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