快速排序输出中的相邻项：算法是否保证它们已被比较？

Question

快速排序算法保证输出数组中相邻项的比较吗？

换句话说： 在排序过程中，快速排序算法在最佳情况下进行 (k-2)2^k+2 次比较，在最佳情况下进行 2^(2k-1)-3*2^(k-1)+1 次比较。最坏的情况，当要排序的元素数量 (N) 表示为 N=2^k-1 时。

这是很多比较，但我们能否确定在算法过程中，输出数组“a”中按排序顺序出现的相邻元素被直接比较至少一次？ 像这样：

cmp(a[1], a[2]); cmp(a[2], a[3]); cmp(a[3], a[4]); ... ; cmp(a[N-1], a[N]);

Answer 1

是的！考虑由各种分区操作形成的树，其中枢轴元素用于与该节点关联的分区。节点在有序遍历中不断增加。对于任何给定的非最大节点，按排序顺序紧随其后的节点要么是祖先（表明当该节点是枢轴时，该节点与其进行比较）要么是后代（表明相反）。

我不确定您如何使用这个保证，但它就在那里。

更一般地，any基于比较的排序算法都具有此属性。考虑两个按排序顺序连续的节点。在某些时候，它们一定是直接相互比较的，因为没有传递性的比较链可以证明左边的比右边的小。

例如，假设排序顺序包含碎片

...foo, bar, baz, qux...

。有可能

foo

和

qux

从未相互比较：它们可以分别与

bar

或

baz

进行比较，或者可以分别与每个进行比较，然后将

bar

和

 进行比较baz

相互比较。但您知道

foo

和

bar

是直接比较的，因为没有其他进程可以确定顺序应该是那个顺序而不是

...bar, foo, baz, qux...

。毕竟，没有其他元素可以帮忙。