神马作文网一道acm的排序题Snow_storm有n（0
来源：学生作业帮 编辑：神马作文网作业帮 分类：数学作业 时间：2024/11/08 02:41:28
一道acm的排序题
Snow_storm有n（0
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次数.
最简单的做法,冒泡法,需要的步数是约小于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次数.