快速排序迭代器要求
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;
是否可以仅使用双向迭代器相当有效地实现快速排序？递归深度仍然可以被保护。
注意。我还没有尝试实际实施。
tl;dr: Is it is possible to implement quicksort on a doubly linked list efficiently? My understanding before thinking about it was, no, its not.
The other day I had an opportunity to consider the iterator requirements for the basic sorting algorithms. The basic O(N²) ones are fairly straightforward.
- Bubble sort - 2 forward iterators will do nicely, one dragging after the other.
- Insertion sort - 2 bidirectional iterators will do. One for the out-of-order element, one for the insertion point.
- Selection sort - A little bit trickier but forward iterators can do the trick.
Quicksort
The introsort_loop in std::sort (as in the gnu standard library/ hp(1994) / silicon graphics(1996) ) requires it to be random_access.
__introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit, _Compare __comp)
As I have come to expect.
Now upon closer inspection I cant find the real reason to require this for quicksort. The only thing that explicitly requires random_access_iterators is the std::__median call that requires the middle element to be calculated. The regular, vanilla quicksort does not calculate the median.
The partitioning consists of a check
if (!(__first < __last))
return __first;
Not really a useful check for bidirectionals. However one should be able to replace this with a check in the previous partitioning travel (from left to right/ right to left) with a simple condition of
if ( __first == __last ) this_partitioning_is_done = true;
Is it possible to implement quicksort fairly efficiently using only bidirectional iterators? The recursive depth can still be guarded.
NB. I have yet not attempted an actual implementation.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您需要随机访问迭代器，因为您通常希望从列表中间选取枢轴元素。如果您选择第一个或最后一个元素作为基准，则双向迭代器就足够了，但对于预排序列表，快速排序会退化为 O(n^2)。
You need random access iterators because you typically want to pick the pivot element from the middle of the list. If you choose the first or last element as the pivot instead, bidirectional iterators are sufficient, but then Quicksort degenerates to O(n^2) for pre-sorted lists.
tl;dr：是的
正如你所说，问题是找到枢轴元素，即中间的元素，用随机访问找到它需要 O(1)，用双向迭代器找到它需要 O(1) O(n)（准确地说是 n/2 次操作）。但是，在每个步骤中，您都必须创建子容器，左侧和右侧分别包含较小和较大的数字。这就是快速排序的主要工作发生的地方，对吗？
现在，在构建子容器（用于递归步骤）时，我的方法是创建一个指向其各自前面元素的迭代器
h。现在，每当您选择下一个元素进入子容器时，只需每隔一次前进h即可。一旦您准备好下降到新的递归步骤，h就会指向枢轴元素。你只需要找到第一个主元，这实际上并不重要，因为 O(n log n + n/2) = O(n log n)。
实际上，这只是运行时优化，但对复杂性没有影响，因为无论您迭代列表一次（将每个值放入各自的子容器中）还是两次（找到枢轴，然后将每个值放入各自的子容器中）子容器）都是相同的：O(2n) = O(n)。
这只是执行时间的问题（而不是复杂性）。
tl;dr: Yes
As you say, the problem is to find the pivot element, which is the element in the middle, finding this with random access takes O(1), finding it with bidirectional iterators takes O(n) (n/2 operations, to be precise). However, in each step you have to create to sub containers, the left and the right containing smaller and bigger numbers respectively. This is where the main work of quick sort takes place, right?
Now, when building the sub containers (for the recursion step) my approach would be to create an iterator
hpointing to their respective front element. Now whenever you choose a next element to go to the sub container, simply advancehevery second time. This will havehpoint to the pivot element once you are ready to descend to the new recursion step.You only have to find the first pivot which does not matter really, because O(n log n + n/2) = O(n log n).
Actually this is just a runtime optimisation, but has no impact on the complexity, because whether you iterate over the list once (to put each value in the respective sub container) or twice (to find the pivot and then put each value in the respective sub container) is all the same: O(2n) = O(n).
It's simply a question of execution time (not complexity).
在双向链表上实现快速排序策略绝对没有问题。 （我认为它也可以很容易地适应单链表）。传统快速排序算法中唯一依赖于随机访问要求的地方是设置阶段，它使用一些“棘手”的东西来选择主元元素。事实上，所有这些“技巧”只不过是启发法，可以用几乎同样有效的顺序方法代替。
我之前已经实现过链表的快速排序。没有什么特别的，您只需要密切注意正确的元素重新链接即可。正如您可能理解的那样，列表排序算法的大部分价值来自这样一个事实：您可以通过重新链接来重新排序元素，而不是显式的值交换。它不仅可以更快，而且（通常更重要的是）还保留可能附加到列表元素的外部引用的值有效性。
PS 但是，我想说，对于链接列表，合并排序算法会产生明显更优雅的实现，并且具有同样良好的性能（除非您正在处理一些专门使用快速排序执行更好的情况）。
There's absolutely no problem with implementing quick-sort strategy on a doubly-linked list. (I think it can also be easily adapted to a singly-linked list as well). The only place in the traditional quick-sort algorithm that depends on the random-access requirement is the setup phase that uses something "tricky" to select the pivot element. In reality all these "tricks" are nothing more than just heuristics that can be replaced with pretty much equally effective sequential methods.
I have implemented quick-sort for linked lists before. There's nothing special about it, you just need to pay close attention to the proper element relinking. As you probably understand, large part of the value of list-sorting algorithms comes from the fact that you can reorder elements by relinking, instead of explicit value-swapping. Not only it could be faster, it also (and often - more importantly) preserves the value-validity of external references that might be attached to the elements of the list.
P.S. However, I'd say that for linked lists the merge-sort algorithm results in a significantly more elegant implementation, which has equally good performance (unless you are dealing with some cases that perform better with quick-sort specifically).