📄 page507.html
字号:
<HTML><HEAD><TITLE>Merging</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html6998" HREF="page508.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6996" HREF="page505.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6990" HREF="page506.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7000" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0015602000000000000000">Merging</A></H3><P>The <tt>merge</tt> method of the <tt>TwoWayMergeSorter</tt> classis defined in Program <A HREF="page507.html#progtwoWayMergeSorterb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.In addition to <tt>self</tt>,this method takes three integer parameters,<tt>left</tt>, <tt>middle</tt>, and <tt>right</tt>.It is assumed that<P> <IMG WIDTH=335 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath69657" SRC="img2086.gif" ><P>Furthermore, it is assumed that the two subsequences of the array,<P> <IMG WIDTH=421 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath69658" SRC="img2087.gif" ><P>and<P> <IMG WIDTH=447 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath69659" SRC="img2088.gif" ><P>are both sorted.The <tt>merge</tt> method merges the two sorted subsequencesusing the temporary array, <tt>_tempArray</tt>.It then copies the merged (and sorted) sequence into the array at<P> <IMG WIDTH=416 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath69660" SRC="img2089.gif" ><P><P><P><A NAME="44523"> </A><A NAME="progtwoWayMergeSorterb"> </A> <IMG WIDTH=575 HEIGHT=447 ALIGN=BOTTOM ALT="program44378" SRC="img2090.gif" ><BR><STRONG>Program:</STRONG> <tt>TwoWayMergeSorter</tt> class <tt>merge</tt> method.<BR><P><P>In order to determine the running time of the <tt>merge</tt> methodit is necessary to recognize that the total number of iterationsof the two loops (lines 7-15, lines 16-19)is <IMG WIDTH=122 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline69665" SRC="img2091.gif" >,in the worst case.The total number of iterations of the third loop (lines 20-21)is the same.Since all the loop bodies do a constant amount of work,the total running time for the <tt>merge</tt> method is <I>O</I>(<I>n</I>),where <IMG WIDTH=152 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline69669" SRC="img2092.gif" > is the total number ofelements in the two subsequences that are merged.<P><HR><A NAME="tex2html6998" HREF="page508.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6996" HREF="page505.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6990" HREF="page506.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7000" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -