数据结构排序算法中元素的平均移动次数如何求比如快速排序和归并排序（二路）算法的平均移动次数

数据结构排序算法中元素的平均移动次数如何求比如快速排序和归并排序（二路）算法的平均移动次数
数据结构排序算法中元素的平均移动次数如何求
比如快速排序和归并排序（二路）算法的平均移动次数

数据结构排序算法中元素的平均移动次数如何求比如快速排序和归并排序（二路）算法的平均移动次数
设X1,X2,……,Xn为有序的n个数,将其随机打乱,设其位置分别为P1,P2,……,Pk.算出每个Xk的移动次数Mk,然后累加后,求期望.
这是最基本的办法,通常也最最复杂.具体到特定的排序算法,可以考虑根据其特定简化计算,就会比较简单了