ds10.2.1.htm

这是清华大学所用的数据结构的电子版教材

&quot;Times New Roman&quot;">；</span><span lang="EN-US"><span style="mso-spacerun:
yes"> </span>//r[j]</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">送</span><span lang="EN-US">r[0]</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">中，使</span><span lang="EN-US">r[j]</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">为待插入记录空位&nbsp; 
    </span><span lang="EN-US"><span style="mso-spacerun: yes"></span>i=j-1</span><span style="font-family:宋体;
mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">；</span><span style="mso-spacerun: yes" lang="EN-US">&nbsp; 
    </span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; letter-spacing: -.6pt">//</span></font><span style="mso-bidi-font-size: 10.0pt; letter-spacing: -.6pt"><font color="#FFFFFF" size="5">从第<span lang="EN-US" style="mso-bidi-font-size: 10.0pt; letter-spacing: -.6pt">i</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; letter-spacing: -.6pt">个记录向前测试插入位置</span>;</font></span></b></li>
  <li>
    <p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">若</span><span lang="EN-US">r[0].key</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">≥</span><span lang="EN-US">r[i].key</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">，转4。</span><span style="mso-spacerun: yes" lang="EN-US">&nbsp;&nbsp;&nbsp; 
    </span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">//</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">插入位置确定</span></font></b></li>
  <li>
    <p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">若</span><span lang="EN-US">r[0].key 
    &lt; r[i].key</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">时，</span><span lang="EN-US">r[i+1]=r[i]</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">；</span><span lang="EN-US">i=i-1</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">；转2。</span></font></b></li>
  <li>
    <p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span lang="EN-US">r[i+1]=r[0]</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">；结束。</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">//</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">存放待插入记录</span></font></b></li>
</ol>
<p class="MsoNormal"><span lang="EN-US"><b><font size="5" color="#FFFFFF">&nbsp;</font></b></span><b><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes" lang="EN-US">&nbsp;&nbsp; 
</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">直接插入排序方法：仅有一个记录的表总是有序的，因此，对</span><span lang="EN-US">n</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">个记录的表，可从第二个记录开始直到第</span><span lang="EN-US">n</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">个记录，逐个向有序表中进行插入操作，从而得到</span><span lang="EN-US">n</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">个记录按关键码有序的表。</span></font></b><span lang="EN-US"><b><font size="5" color="#FFFFFF">&nbsp;<o:p>
</o:p>
</font></b></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;"><font color="#FFFF00"><b><font size="5">【算法</font></b></font></span><font color="#FFFF00"><b><font size="5"><span lang="EN-US">10.2</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">】</span></font></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><b><font size="5" color="#FFFFFF">void<span style="mso-spacerun: yes">&nbsp;&nbsp;