数学建模社区-数学中国

标题: 一个简单问题，觉得书上写得有问题。 [打印本页]
作者: 火元素    时间: 2005-1-20 17:47
标题: 一个简单问题，觉得书上写得有问题。
<>是一个插入排序的小程序：</P>* E8 X, t6 j% h' I3 Z" }# u% E
<>public void insertionsort(Object[] data) {</P>  z* U' c. }# }8 Z' w2 i% U1 Q
<>    Comparable tmp;</P>6 u0 v, L4 _2 i, R/ \& i
<>    int i, j;</P>5 P# Z: _1 I1 G9 Q8 E
<>    for(i = 1; i &lt; data.length; i++) {</P>
' [" v  W+ p, Q" u. P' C4 }$ O<>       tmp = (Comparable)data;</P>! j% ]) m+ J- D; _! B5 K
<>       for(j = i;  j &gt; 0 &amp;&amp; tmp.comparaTo(data[j - 1]) &lt;  ０; j--)</P>
9 p6 f4 Q! w- V5 v% T<>            data[j] = data[j -1];</P>3 m! H: T7 p# `; ]$ f
<>       data[j] = tmp;</P>" f0 }* `0 \1 z$ q
<>    }</P>. c) v% ^- W* k  n! S6 U
<>}</P>
8 X0 d0 ^/ C2 D3 a/ A<>书上说移动次数有（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