数学建模社区-数学中国

标题: 一个简单问题，觉得书上写得有问题。 [打印本页]
作者: 火元素    时间: 2005-1-20 17:47
标题: 一个简单问题，觉得书上写得有问题。
<>是一个插入排序的小程序：</P>
- G- k0 ?6 A& Q; x/ S! _<>public void insertionsort(Object[] data) {</P>7 o- r+ }1 _  t( z
<>    Comparable tmp;</P>
3 F' M3 O' b* p8 F: t0 [9 J<>    int i, j;</P>! ^% M0 T, z( V+ R3 ^; b; F
<>    for(i = 1; i &lt; data.length; i++) {</P>
% g( ]9 Z8 `; I5 Q9 U/ E  i<>       tmp = (Comparable)data;</P>
4 z- [6 M; Q2 l0 p<>       for(j = i;  j &gt; 0 &amp;&amp; tmp.comparaTo(data[j - 1]) &lt;  ０; j--)</P>7 R* ]8 y! }' D
<>            data[j] = data[j -1];</P>* J. ]% q+ O6 u; |: p5 O  k
<>       data[j] = tmp;</P>
* o! A$ G* j9 X, {0 Y7 X& v<>    }</P>
& M1 t& v; Q; Z! F" `) t<>}</P>$ j4 M& v$ a& w0 I  V/ Y
<>书上说移动次数有（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