对5个数排序最少的比较次数像我这样为什么不对考虑两个数最多一次；3个,交换一次使一个数回原位,在交换一次,2次；4个,交换一次使一个数回原位,剩下的是三个,1+2次；5个,同理,1+3次好吧

Question

对5个数排序最少的比较次数 像我这样为什么不对
考虑两个数 最多一次 ；3个,交换一次使一个数回原位,在交换一次,2次；4个,交换一次使一个数回原位,剩下的是三个,1+2次；5个,同理,1+3次
好吧,我自己解决了.这道题意思应该是对5个数的随机序列排序,最差情况下的比较次数最少是7次.就是说你编写一个排序算法对长度为5的序列排序,要达到无论序列处于哪一种排列,比较次数不超过N,则N> =7.否则单纯论“最少比较次数”,那4次就够了.

Answer 1

语言表达不清,但能模模糊糊看懂些
很简单,你的算法 其实是 按照 临近2个数这么比较的 当只有3个数的时候可以这么用
但超过3个数时,比如 四个数时,就不能这么算了
4 3 2 1 按照你的说法,从4开始 比岛最后 用了 三次 最后得出的结论是 4最大 此时序列是 3214
接着 要从三开始 比到1就可以了 ,也就是一共三个数要比较 需要2次 此时序列是 2134
最后 再从2开始 比到1 一共2个数比较 花了一次 ,这时候结果才是1234
所以一共花了 3+2+1=6次
可以得出公式 有几个数 要排几次：
设一共有 x个数,需要y次才能拍完
他们之间的关系是
y=（x-1)~
表示阶加的意思
例如 意思是 5+4+ 3+2+1=15
非常简单