快速排序算法能否保证输出数组中相邻项的直接比较?
换句话说: 在排序过程中,快速排序算法在最佳情况下进行 (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]);
是的!考虑由各种分区操作形成的树,其中枢轴元素用于与该节点关联的分区。节点在有序遍历中不断增加。对于任何给定的非最大节点,按排序顺序紧随其后的节点要么是祖先(表明当该节点是枢轴时,该节点与其进行比较)要么是后代(表明相反)。
我不确定您如何使用这个保证,但它就在那里。
更一般地,any基于比较的排序算法都具有此属性。考虑两个按排序顺序连续的节点。在某些时候,它们一定是直接相互比较的,因为没有传递性的比较链可以证明左边的比右边的小。
例如,假设排序顺序包含碎片
...foo, bar, baz, qux...
。有可能 foo
和 qux
从未相互比较:它们可以分别与 bar
或 baz
进行比较,或者可以分别与每个比较,然后将 bar
和 进行比较baz
相互比较。但您知道 foo
和 bar
是直接比较的,因为没有其他进程可以确定顺序应该是那个顺序而不是 ...bar, foo, baz, qux...
。毕竟,没有其他元素可以帮忙。