数学建模社区-数学中国

标题: 一个简单问题，觉得书上写得有问题。 [打印本页]
作者: 火元素    时间: 2005-1-20 17:47
标题: 一个简单问题，觉得书上写得有问题。
<>是一个插入排序的小程序：</P>1 `5 Z- q' o. A
<>public void insertionsort(Object[] data) {</P>- B4 b2 f' p$ L2 K1 w
<>    Comparable tmp;</P>1 o8 X6 y, |" }5 j& C1 L
<>    int i, j;</P>$ p1 H1 m' P5 E1 X: l* O
<>    for(i = 1; i &lt; data.length; i++) {</P>1 V( E4 }3 T8 g1 c9 v8 O
<>       tmp = (Comparable)data;</P>2 V! T8 x. c9 g( |: T
<>       for(j = i;  j &gt; 0 &amp;&amp; tmp.comparaTo(data[j - 1]) &lt;  ０; j--)</P>4 Y& q. i- d( j3 m2 f6 E
<>            data[j] = data[j -1];</P>  [/ B2 D- _6 F2 ]- s. G, h+ L% ]/ d
<>       data[j] = tmp;</P>
0 |* `5 q3 I5 G<>    }</P>
3 |3 ^- k3 O' n0 f3 |<>}</P>
# J' c* d$ \6 M) x7 b7 j<>书上说移动次数有（n*n + 5n -6) / 4次。感觉有问题。</P>
作者: ilikenba    时间: 2005-1-20 21:41
<>如果说这样的一个步骤data[j] = data[j -1];定义为一个移动的话；最坏的情况下应该是移动n*(n-1)/2次吧！</P>
作者: devil2k    时间: 2005-6-15 17:36
不知道



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5