?? page502.html
字號:
<HTML>
<HEAD>
<TITLE>Straight Selection Sorting</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="tex2html8121" HREF="page503.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page503.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="tex2html8119" HREF="page501.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page501.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="tex2html8113" HREF="page501.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page501.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="tex2html8123" 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="tex2html8124" 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>
<H2><A NAME="SECTION0016510000000000000000">Straight Selection Sorting</A></H2>
<P>
The simplest of the selection sorts is called
<em>straight selection</em><A NAME=38076> </A>.
Figure <A HREF="page502.html#figsort4" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page502.html#figsort4"><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 straight selection works.
In the version shown,
the sorted list is constructed from the right
(i.e., from the largest to the smallest element values).
<P>
<P><A NAME="39236"> </A><A NAME="figsort4"> </A> <IMG WIDTH=575 HEIGHT=546 ALIGN=BOTTOM ALT="figure38078" SRC="img2183.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2183.gif" ><BR>
<STRONG>Figure:</STRONG> Straight Selection Sorting<BR>
<P>
<P>
At each step of the algorithm,
a linear search of the unsorted elements is made
in order to determine the position of the largest remaining element.
That element is then moved into the correct position of the array
by swapping it with the element which currently occupies that position.
<P>
For example, in the first step shown in Figure <A HREF="page502.html#figsort4" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page502.html#figsort4"><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>,
a linear search of the entire array reveals that 9 is the largest element.
Since 9 is the largest element, it belongs in the last array position.
To move it there, we swap it with the 4 that initially occupies that position.
The second step of the algorithm identifies 6 as the largest remaining
element an moves it next to the 9.
Each subsequent step of the algorithm moves
one element into its final position.
Therefore, the algorithm is done after <I>n</I>-1 such steps.
<P>
<BR> <HR>
<UL>
<LI> <A NAME="tex2html8125" HREF="page503.html#SECTION0016511000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page503.html#SECTION0016511000000000000000">Implementation</A>
</UL>
<HR><A NAME="tex2html8121" HREF="page503.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page503.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="tex2html8119" HREF="page501.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page501.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="tex2html8113" HREF="page501.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page501.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="tex2html8123" 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="tex2html8124" 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 + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -