一道acm的排序题Snow_storm有n(0

来源:学生作业帮助网 编辑:作业帮 时间:2024/05/01 10:29:32
一道acm的排序题Snow_storm有n(0

一道acm的排序题Snow_storm有n(0
一道acm的排序题
Snow_storm有n(0

一道acm的排序题Snow_storm有n(0
首先这不是排序题目,而是已知顺序通过两两交换达到这个顺序.
最简单的做法,冒泡法,需要的步数是约小于n-1(如果某一步正好最小的在第一位,那么就不需要交换.总的期望步数是n-(1/1)-(1/2)-(1/3)-(1/4)-...-(1/n)).这个答案显然不是竞赛该有的.
如果打乱顺序之后,卡片位置是纯随机的,我现在能想到的最优步数是n/2(假设n=2^k,否则略多.以下按n=2^k讨论):
第一步:对前2张卡片排序,使之正好满足前4张交换时,不需要额外步数
第二步:对前4张卡片排序,使之正好满足前8张交换时,不需要额外步数
...
第k-1步:对前2^k张卡片排序.结束.
由于排序是完全随机的,第k步的期望交换次数是2^(k-1)次,因此,整体的期望交换次数是n/2-1/2次.比开始说的最简方法节约近1/2次数.