八、（6分）冒泡排序法的基本思想是交换所有的相邻逆序,直到没有逆序为止.假设冒泡排序算法的输入是个不同数的一个随机排序,即等可能地为个不同数的!种排列中的任意一个,求冒泡法需

Question

八、（6分） 冒泡排序法的基本思想是交换所有的相邻逆序,直到没有逆序为止.假设冒泡排序算法的输入是个不同数的一个随机排序,即等可能地为个不同数的!种排列中的任意一个,求冒泡法需要交换逆序的次数的期望值.

Answer 1

设总共n个不同的数,不妨设这n个数为　1,2,...,n．
设　a1a2．．．an　为一个排序.
任给　1＜＝i＜j＜＝n．　设as＝i,　at＝j,
如果s＞t,则必有且只有一次交换逆序正好把　．．．ji．．．　换成　．．．ij．．．.
如果s＜t,则没有这样的交换逆序.
如果我们同时考虑两个排序：
a1a2．．．an
an．．．a2a1
则任意一个　ij交换逆序只可能在其中一个出现,也必在其中一个出现.所以两者的交换逆序次数总和不变.
12...n　的交换逆序次数为0
而
n．．．21的交换逆序次数为（n－1）!
所以　冒泡法需要交换逆序的次数的期望值＝（n－1）!／2