page511.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 52 行
HTML
52 行
<HTML>
<HEAD>
<TITLE>Merging</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html8229" HREF="page512.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page512.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html8227" HREF="page509.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page509.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html8221" HREF="page510.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page510.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html8231" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html8232" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H3><A NAME="SECTION0016602000000000000000">Merging</A></H3>
<P>
The <tt>Merge</tt> function of the <tt>TwoWayMergeSorter<T></tt> class
is defined in Program <A HREF="page511.html#progsorter11c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page511.html#progsorter11c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
Altogether, this function takes four parameters:
The first is a reference to the array to be sorted.
The remaining three, <tt>left</tt>, <tt>middle</tt>, and <tt>right</tt>,
are unsigned integers.
It is assumed that
<P> <IMG WIDTH=335 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath70453" SRC="img2202.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2202.gif" ><P>
Furthermore, it is assumed that the two subsequences of the array,
<P> <IMG WIDTH=422 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath70454" SRC="img2203.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2203.gif" ><P>
and
<P> <IMG WIDTH=447 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath70455" SRC="img2204.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2204.gif" ><P>
are both sorted.
The <tt>Merge</tt> routine merges the two sorted subsequences
using the temporary array specified by <tt>tempArray</tt>.
It then copies the merged (and sorted) sequence into the array at
<P> <IMG WIDTH=417 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath70456" SRC="img2205.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2205.gif" ><P>
<P>
<P><A NAME="44736"> </A><A NAME="progsorter11c"> </A> <IMG WIDTH=575 HEIGHT=409 ALIGN=BOTTOM ALT="program44595" SRC="img2206.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2206.gif" ><BR>
<STRONG>Program:</STRONG> <tt>TwoWayMergeSorter<T></tt> Class <tt>Merge</tt> Member Function Definition<BR>
<P>
<P>
In order to determine the running time of the <tt>Merge</tt> routine
it is necessary to recognize that the total number of iterations
of the three loops (lines 8-14, lines 15-16, and lines 17-18)
is <IMG WIDTH=122 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70461" SRC="img2207.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2207.gif" >.
The total number of iterations of the fourth loop (lines 19-20)
is the same.
Since all the loop bodies do a constant amount of work,
the total running time for the <tt>Merge</tt> routine is <I>O</I>(<I>n</I>),
where <IMG WIDTH=152 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70465" SRC="img2208.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2208.gif" > is the total number of
elements in the two subsequences that are merged.
<P>
<HR><A NAME="tex2html8229" HREF="page512.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page512.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html8227" HREF="page509.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page509.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html8221" HREF="page510.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page510.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html8231" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html8232" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?