在平均情況下排序數據的快速排序有多少？

Question

我在stakoverflow的兩個答案之間混淆，

我的問題是有多少交換quicksort採取在avg情況下排序數據？

下面是一些鏈接話說平均

（1/3）NLN（n）的交換link 1(in 1st answer -"Analyse abstract basic operations")

ref link 2 (page no-20 in slide)

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

交換

link 1

ref link 2 (in last-"And as summary")

我想知道哪一個是正確的？

Answer 1

從您的最後一個環節推導說：

我們假設一個迭代過程中交換的平均數是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）。