请教一道CS_SUB题目

Elaine.WUID: 184092

题目:冒泡排序,A[1..n],已经从A[1]排序到A[i],问A[i]与A[i+1]交换的概率.


我的疑问:既然从A[1]到A[i]已经排序好了,那A[i]肯定要小于A[i+1]啊(如果是最小的放在最前面)?那么A[i]与A[i+1]肯定就不会需要交换的了?

pengodUID: 136708

不是啊。。假设排到现在是这种情况，小的上升冒泡到最前面

数值     2 3 4 5 6 7 8 9 10 1
i值       1 2 3 4 5 6 7 8  9  10
a[i] = 10, a[i+1] = 1
总之无论大的还是小的冒泡
a[i]是前面i个值的最大或者最小的。那么第i+1个元素的值要是这i+1个中最小的或者最大的可能性是1/(i+1), 不是最大或者最小的概率就是1-1/(i+1), 也就是i/(i+1)...也就是这种情况下需要交换啊
看看黄蔚的书吧，这小子讲的很清楚，赞一个。他在huawei混的也挺好，呵呵

Elaine.WUID: 184092

可是按照规则,要从最后一个元素向前俩俩交换,那么对于你的这个数组,
数值     2 3 4 5 6 7 8 9 10 1
i值       1 2 3 4 5 6 7 8  9  10
第一趟的时候就应该把最小的元素"1" 给排到第一的位置上去了啊.怎么还会出现现在这样的情况那?

headlongUID: 34796

Elaine.W，你说的对。这道题目有错误。

如果是冒泡排序，不需要交换A[i]和A[i+1]。应该选择0。但是题目选项中没有0，只有
(A) 1/2  (B) i/(i+1)  (C) 1/n  (D) n/2

这是一道回忆题，所以或者应该在选项中加入(E) 0；或者把冒泡排序改为直接插入排序。

Elaine.WUID: 184092

多谢~