快速排序输出中的相邻项:算法是否保证它们已被直接比较?

问题描述 投票:0回答:1

快速排序算法能否保证输出数组中相邻项的直接比较?

换句话说: 在排序过程中,快速排序算法在最佳情况下进行 (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]);
algorithm sorting quicksort
1个回答
1
投票

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

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

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

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

...foo, bar, baz, qux...
。有可能
foo
qux
从未相互比较:它们可以分别与
bar
baz
进行比较,或者可以分别与每个比较,然后将
bar
 进行比较baz
相互比较。但您知道
foo
bar
是直接比较的,因为没有其他进程可以确定顺序应该是那个顺序而不是
...bar, foo, baz, qux...
。毕竟,没有其他元素可以帮忙。

© www.soinside.com 2019 - 2024. All rights reserved.