顺排序变成逆排序的问题（段位制的编辑）

noski

对，的确可以看成是N个，那么这样编程会容易一点吧。不知各种程序语言函数库中的逆序函数，有没有这个效率高。<BR>
不过，数字过大时会让人感觉不够好。比如我有201个数字，那么N＝100。你的说法是每次都挪100个数字，挪101次；而我的说法是只有一次需要挪100个数字，其余100次只要每次挪两个数字。当然两个实质是一回事。要是用链表的话，就打断再接上就行了。。

金眼睛

<P>哈哈，noski对数字还真是敏感，强，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> </P>
<P>&nbsp;</P>
<P>虽然也编了程序，但没想到这其中会有规律，所以只运行到6，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/sweat.gif" border=0 smilieid="10"> ，其实利用指针，程序不大，就是比较耗时。</P>
<P>&nbsp;</P>
<P>我把noski的规律再补充一下吧，别告我侵权啊，呵呵！！</P>
<P>&nbsp;</P>
<P>我觉得第一步移动1，2规律性不强，对于13，应该进行如下操作(借用大烟头的符号)：</P>
<P>&nbsp;</P>
<P>0：1，（2，3，4，5，6，7），8，9，10，11，12，13 /</P>
<P>1：/1，8，9，10，11，12，（13 ，2），3，4，5，6，7</P>
<P>2：13&nbsp;&nbsp;/&nbsp;&nbsp;&nbsp;2，1，8，9，10，11，（12，3），4，5，6，7</P>
<P>3：13，12&nbsp;&nbsp;/&nbsp;&nbsp;3，&nbsp;2，1，8，9，10，（11，4），5，6，7</P>
<P>4：13，12，11&nbsp;&nbsp;/&nbsp;&nbsp;4，3，&nbsp;2，1，8，9，（10，5），6，7</P>
<P>5：13，12，11，10&nbsp;&nbsp;/&nbsp;&nbsp;5，4，3，&nbsp;2，1，8，（9，6），7</P>
<P>6：13，12，11，10，9&nbsp;&nbsp;/&nbsp;&nbsp;6，5，4，3，&nbsp;2，1，（8，7）</P>
<P>7：13，12，11，10，9，8，7，6，5，4，3，&nbsp;2，1</P>
<P>&nbsp;</P>
<P>对于12，第一步为：（1，2，3，4，5，6），7，8，9，10，11，12 /</P>
<P>&nbsp;</P>
<P>这样可以很明显的看出：</P>
<P>对于N（奇数）步数为：(N-1)/2+1=(N+1)/2</P>
<P>对于N（偶数）步数为：N/2+1</P>
<P>&nbsp;</P>

[ 本帖最后由 金眼睛 于 2008-9-10 21:56 编辑 ]

noski

赞！这样一来规律性就更强了，一下子就能看出来移动的目的。<BR>
先前后颠倒，再两个两个解决。你17楼说的函数flipud()的算法，不知有没有这个高效

ares_g

33楼有几只金眼睛，也分我一只吧

ggglgq

&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp; 呵呵，数学高手们都云集到这里来了，看样子这个问题离解决的日子不遥远了！<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/handshake.gif" border=0 smilieid="17">&nbsp;<BR>&nbsp;&nbsp;<BR>&nbsp;&nbsp;<BR>&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;<BR>&nbsp;

ares_g

如果是一个由互不相等的自然数随机排列的有限数列，那最多要几步完成排序呀？

noski

我这样想的：要是可以把数字的乱序度看成“熵”一样的话，比如设定一个数字其后面有几个比它大的，熵就加几。那么题中从正序到逆序，就是最乱的情况。所以N个随机打乱的数字排序的最少步数最多也就是33#那么多。

金眼睛

<P><STRONG>回复34#的帖子</STRONG></P>
<P><STRONG></STRONG>&nbsp;</P>
<P>呵呵，我也不太清楚flipud()具体的算法，我测试了一下，1万个数需要0.016秒，也说不定是一个一个往前提吧？呵呵！</P>
<P>&nbsp;</P>
<P><STRONG>回复35#的帖子</STRONG></P>
<P><STRONG></STRONG>&nbsp;</P>
<P>我要是二郎神就好了，肯定给你一个，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/loveliness.gif" border=0 smilieid="28"> </P>
<P>&nbsp;</P>
<P>对于随机序列，各种排序算法的算法复杂度不同。不过由于lucky case，同一个算法复杂度下，运行时间也不一样吧！</P>

Cielo

<P>哇太厉害了！能发现这样的规律<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/smile.gif" border=0 smilieid="1"> </P>
<P>&nbsp;</P>
<P>想问一下，如何证明那就是最少步了呢？</P>

大烟头

13个数字随机排列，那最远状态的最少步是几步呢？