首页 > 试题广场 >

已知待排序的三个整数a,b和c(a≠b≠c≠a)可能出现的六

[问答题]

已知待排序的三个整数a,b和c(a≠b≠c≠a)可能出现的六种排列情况的概率不等,且如下表所示:

a<b<c

b<a<c

a<c<b

c<a<b

b<c<a

c<b<a

0.13

0.24

0.08

0.19

0.20

0.16

试为该序列设计一个最佳排序方案, 使排序过程中所需进行的关键字间的比较次数的期望值达到最小。


题目只要求比较次数期望值最小而没有对交换次数做要求。
假设初始序列为a,b,c那么只要c不为最大,那么就需要比较三次,因为a与b进行第一次比较以后,c必须和a、b都比较才能确定顺序。也就是说,只有初始序列最后一个数是最大的时候才可以只用比较两次,否则需要比较三次,所以当初始序列为a,b,c或者b,a,c时比较次数的期望值最小
发表于 2019-10-01 18:24:00 回复(0)