page508.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 76 行
HTML
76 行
<HTML>
<HEAD>
<TITLE>The Sorting Phase</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="tex2html8189" HREF="page509.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page509.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="tex2html8187" HREF="page506.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page506.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="tex2html8183" HREF="page507.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page507.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="tex2html8191" 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="tex2html8192" 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="SECTION0016532000000000000000">The Sorting Phase</A></H3>
<P>
Once the max heap has been built,
heapsort proceeds to the selection sorting phase.
In this phase the sorted sequence is obtained
by repeatedly withdrawing the largest element from the max heap.
Figure <A HREF="page508.html#figsort6" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page508.html#figsort6"><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> illustrates how this is done.
<P>
<P><A NAME="42812"> </A><A NAME="figsort6"> </A> <IMG WIDTH=575 HEIGHT=567 ALIGN=BOTTOM ALT="figure41101" SRC="img2197.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2197.gif" ><BR>
<STRONG>Figure:</STRONG> Heap Sorting<BR>
<P>
<P>
The largest element of the heap is always found at the root
and the root of a complete tree is always in array position one.
Suppose the heap occupies array positions 1 through <I>k</I>.
When an element is withdrawn from the heap,
its length decreases by one.
I.e., after the withdrawal the heap occupies array positions 1 through <I>k</I>-1.
Thus, array position <I>k</I> is no longer required by the max heap.
However, the next element of the sorted sequence belongs in position <I>k</I>!
<P>
So, the sorting phase of heapsort works like this:
We repeatedly swap the largest element in the heap (always in position 1)
into the next position of the sorted sequence.
After each such swap,
there is a new value at the root of the heap and
this new value is pushed down into the correct position in the heap
using the <tt>PercolateDown</tt> routine.
<P>
Program <A HREF="page508.html#progsorter10c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page508.html#progsorter10c"><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> gives the <tt>DoSort</tt> routine
of the <tt>HeapSorter<T></tt> class.
The <tt>DoSort</tt> routine embodies both phases of the heapsort algorithm.
However, before it starts the first phase of the algorithm,
<tt>DoSort</tt> sets the array base to one.
This modification of the array base simplifies the coding of the algorithms.
As discussed in Section <A HREF="page485.html#secsortingsorters" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page485.html#secsortingsorters"><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>
the array base will have been set to zero by the
<tt>Sort</tt> member function of the <tt>Sorter<T></tt> base class
and will be restored to the original base by that routine.
<P>
<P><A NAME="43052"> </A><A NAME="progsorter10c"> </A> <IMG WIDTH=575 HEIGHT=218 ALIGN=BOTTOM ALT="program42824" SRC="img2198.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2198.gif" ><BR>
<STRONG>Program:</STRONG> <tt>HeapSorter<T></tt> Class <tt>DoSort</tt> Member Function Definition<BR>
<P>
<P>
In the first phase of heapsort
the <tt>BuildHeap</tt> routine is called to transform
the array into a max heap.
As discussed above, this is done in <I>O</I>(<I>n</I>) time.
<P>
The second phase of the heapsort algorithm builds the sorted list.
In all <I>n</I>-1 iterations of the loop on lines 6-10 are required.
Each iteration involves one swap
followed by a <tt>PercolateDown</tt> operation.
Since the worst-case running time for <tt>PercolateDown</tt> is <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59891" SRC="img403.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img403.gif" >,
the total running time of the loop is <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59897" SRC="img405.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img405.gif" >.
The running time of the second phase asymptotically dominates
that of the first phase.
As a result, the worst-case running time of heapsort is <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59897" SRC="img405.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img405.gif" >.
<P>
<HR><A NAME="tex2html8189" HREF="page509.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page509.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="tex2html8187" HREF="page506.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page506.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="tex2html8183" HREF="page507.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page507.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="tex2html8191" 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="tex2html8192" 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 + -
显示快捷键?