在平均情况下排序数据的快速排序有多少？

问题描述：

我的问题是有多少交换quicksort采取在avg情况下排序数据？

下面是一些链接话说平均

其他链接提示1 * N * LN（N）平均

交换

我想知道哪一个是正确的？

这可能会更适合[cs.se]。 – Dukeling

答

从您的最后一个环节推导说：

我们假设一个迭代过程中交换的平均数是1 /∙（N-1）。这意味着平均只有一半的元素被交换。

首先，他们所谓的交换次数似乎是写入次数而不是交换次数。所以，假设他们的交换总数应该是（1/2）∙n∙ln（n）。其次，我不认为这个假设是正确的（如果枢纽一直是中位数而不是随机选择的话）。

假定阵列{X ，X ，...，X _Ñ}是{1，2，...，N}的随机置换，和z是一个随机选择的枢。快速排序算法的第一次迭代期间的交换次数是来自{1，...，n}的下标i的数量，使得我可以得到这样的索引i的数量，即i < = z和x _i> z。使得数的期望值为：

Σ_{K = 1 ... N}（P（Z = k）的∙Σ我≤ķ（P（X > k））的）
=（1/n）的∙Σ_{K = 1 ... N}（Σ我≤ķ（（NK）/ N））
=（1/n）的∙Σ_{K = 1 ... n}（k∙（nk）/ n）
=（1/6）（n-1）（n + 1）/ n
≈n/6

而且由于平均迭代次数是2∙ln（n），交换总次数是（1/3）∙n∙ln（n）。