快速排序算法保证输出数组中相邻项的比较吗？
换句话说： 在排序过程中，快速排序算法在最佳情况下进行 (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]);
是的！考虑由各种分区操作形成的树，其中枢轴元素用于与该节点关联的分区。节点在中序遍历中递增，对于任何给定的非最大节点，按排序顺序紧随其后的节点要么是祖先（表明当该节点是枢轴时，该节点与其进行比较），要么后代（表示相反）。
我不确定您如何使用这个保证，但它就在那里。