📄 9_2.htm

📁 辅助学习帮助大家学习
💻 HTM
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=gb_2312-80">
<META NAME="Generator" CONTENT="Microsoft Word 97">
<TITLE>第 2 章  线性表</TITLE>
</HEAD>
<BODY>

<B><FONT SIZE=3><P ALIGN="JUSTIFY">2. </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>希尔排序算法</P>
</B><P ALIGN="JUSTIFY">&#9;</FONT><B><FONT SIZE=3>void</B>  Shellinsert ( SqList  <B>&amp;</B>L,  <B>int</B>  dk )  </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B><P ALIGN="JUSTIFY">&#9;</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>对顺序表</FONT><FONT SIZE=3> <I>L</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>作一趟希尔插入排序。此算法和一趟直接插入排序相比，作了以下修改：</P>
<P ALIGN="JUSTIFY">&#9;</FONT><FONT SIZE=3>// (1) </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>前后记录为止的增量是</FONT><FONT SIZE=3> <I>dk</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，而不是</FONT><FONT SIZE=3> 1</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>；</P>
<P ALIGN="JUSTIFY">&#9;</FONT><FONT SIZE=3>// (2) <I>r</I>[0] </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>只是暂存单元，而不是哨兵。当</FONT><FONT SIZE=3> <I>j</I> &lt;= 0 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>时，插入位置已经找到。</P>
<P ALIGN="JUSTIFY">&#9;</FONT><FONT SIZE=3>  <B>for</B> ( i = dk+1;  i &lt;=L.length;  ++i )</P>
</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">&#9;&#9;</FONT><B><FONT SIZE=3>if</B> ( L.r[i].key &lt; L.r[i-dk].key )  </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{&#9;&#9;&#9;&#9;</B></FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>需要将</FONT><FONT SIZE=3> <I>L.</I>r[<I>i</I>] </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>插入有序增量子表</P>
<P ALIGN="JUSTIFY">&#9;&#9;</FONT><FONT SIZE=3>  L.r[0] = L.r[i];&#9;&#9;&#9;&#9;&#9;&#9;&#9;// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>暂存在</FONT><FONT SIZE=3> <I>L</I>.r[0]</P>
</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">&#9;&#9;</FONT><FONT SIZE=3>  <B>for</B> ( j = i-dk;  j &gt; 0 <B>&amp;&amp;</B> ( L.r[0].key &lt; L.r[j].key );  j -= dk )</P>
<P ALIGN="JUSTIFY">&#9;&#9;&#9;L.r[j+dk] = L.r[j];&#9;&#9;&#9;&#9;&#9;&#9;// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>记录后移，查找插入位置</P>
<P ALIGN="JUSTIFY">&#9;&#9;</FONT><FONT SIZE=3>  L.r[j+dk] = L.r[0];&#9;&#9;&#9;&#9;&#9;&#9;// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>插入到正确位置</P>
<P ALIGN="JUSTIFY">&#9;&#9;<B>}</B></FONT><FONT SIZE=3> // if </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
<P ALIGN="JUSTIFY">&#9;<B>}</B></FONT><FONT SIZE=3> // ShellInsert</P></FONT></BODY>
</HTML>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -