📄 9_7.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">7. </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>归并排序算法</P>
</B><P ALIGN="JUSTIFY">	</FONT><B><FONT SIZE=3>typedef</B> SqList RcdType;</P>
<P ALIGN="JUSTIFY"></P>
<P ALIGN="JUSTIFY">	<B>void</B> Merge ( RcdType SR[ ], RcdType <B>&</B>T[ ], <B>int</B> i, <B>int</B> m, <B>int</B> n ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将有序的</FONT><FONT SIZE=3> <I>SR</I>[<I>i</I> . . <I>m</I>] </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>和</FONT><FONT SIZE=3> <I>SR</I>[<I>m</I>+1 . . <I>n</I>] </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>归并为有序的</FONT><FONT SIZE=3> <I>TR</I>[<I>i</I> . . <I>n</I>]</P>
<P ALIGN="JUSTIFY">	 <B>for</B> ( j = m+1, k = i; i <= m <B>&&</B> j < = n; ++k ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> // </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将</FONT><FONT SIZE=3> <I>SR</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>中记录由小到大地并入</FONT><FONT SIZE=3> <I>TR</P>
</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">		</FONT><B><FONT SIZE=3>if</B> ( SR[i].key < = SR[j].key ) TR[k] = SR[i++];</P>
<P ALIGN="JUSTIFY">		<B>else</B> TR[k] = SR[j++];</P>
<P ALIGN="JUSTIFY">	 </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> // for </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> <B>if</B> ( i < = m ) TR[k . . n] = SR[i . . m];			// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将剩余的</FONT><FONT SIZE=3> <I>SR</I>[<I>i</I> . . <I>m</I>] </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>复制到</FONT><FONT SIZE=3> <I>TR</P>
</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> <B>if</B> ( j < = n ) TR[k . . n] = SR[j . . n];				// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将剩余的</FONT><FONT SIZE=3> <I>SR</I>[<I>j</I> . . <I>n</I>] </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>复制到</FONT><FONT SIZE=3> <I>TR</P>
</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">	<B>}</B></FONT><FONT SIZE=3> // Merge</P>
<P ALIGN="JUSTIFY"></P>
<P ALIGN="JUSTIFY">	<B>void</B> MSort ( RcdType SR[ ], RcdType <B>&</B>TR1[ ], <B>int</B> s, <B>int</B> t ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将</FONT><FONT SIZE=3> <I>SR</I>[<I>s</I> . . <I>t</I>] </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>归并排序为</FONT><FONT SIZE=3> <I>TR</I>1[<I>s</I> . . <I>t</I>]</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>。</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> <B>if</B> ( s = = t ) TR1[s] = SR[s];</P>
<P ALIGN="JUSTIFY">	 <B>else {</P>
</B></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3>m = ( s + t ) / 2;							// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将</FONT><I><FONT SIZE=3>SR</I>[<I>s .. t</I>]</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>平分为</FONT><FONT SIZE=3> <I>SR</I>[<I>s .. m</I>]</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>和</FONT><I><FONT SIZE=3>SR</I>[<I>m</I>+1 .. <I>t</I>]</P>
</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3>MSort ( SR, TR2, s, m );						// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>递归地将</FONT><I><FONT SIZE=3>SR</I>[<I>s </I>.. <I>m</I>]</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>归并为有序的</FONT><I><FONT SIZE=3>TR</I>2[<I>s </I>.. <I>m</I>]</P>
</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3>MSort ( SR, TR2, m+1, t );					// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>递归地将</FONT><I><FONT SIZE=3>SR</I>[<I>m</I>+1.. <I>t</I>]</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>归并为有序的</FONT><I><FONT SIZE=3>TR</I>2[<I>m</I>+1.. <I>t</I>]</P>
</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3>Merge ( TR2, TR1, s, m, t );					// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将</FONT><I><FONT SIZE=3>TR</I>2[<I>s </I>.. <I>m</I>]</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>和</FONT><I><FONT SIZE=3>TR</I>2[<I>m</I>+1..<I>t</I>]</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>归并到</FONT><I><FONT SIZE=3>TR</I>1[<I>s </I>.. <I>t</I>] </P>
</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> // else </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
<P ALIGN="JUSTIFY">	<B>}</B></FONT><FONT SIZE=3> // MSort</P>
<P ALIGN="JUSTIFY"></P>
<P ALIGN="JUSTIFY">	<B>void</B> MergeSort ( SqList <B>&</B>L ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B><P ALIGN="JUSTIFY">	</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">	</FONT><FONT SIZE=3> MSort ( L.r, L.r, 1, L.length );</P>
<P ALIGN="JUSTIFY">	</FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> // MergeSort</P></FONT></BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -