page479.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 69 行
HTML
69 行
<HTML><HEAD><TITLE>Basics</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="tex2html6685" HREF="page480.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6683" HREF="page478.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6677" HREF="page478.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6687" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0015100000000000000000">Basics</A></H1><P>Consider an arbitrary sequence <IMG WIDTH=156 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68897" SRC="img1975.gif" >comprised of of <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" > elements drawn from a some universal set <I>U</I>.The goal of <em>sorting</em> is to rearrange the elements of <I>S</I>to produce a new sequence, say <I>S</I>',in which the elements of <I>S</I> appear <em>in order</em>.<P>But what does it mean for the elements of <I>S</I>' to be <em>in order</em>?We shall assume that there is a relation, <I><</I>,defined over the universe <I>U</I>.The relation <I><</I> must be a <em>total order</em>,which is defined as follows:<P><BLOCKQUOTE> <b>Definition</b><A NAME="defntotalorder"> </A>A <em>total order</em><A NAME=34348> </A> is a relation, say <I><</I>,defined on the elements of some universal set <I>U</I>with the following properties:<OL><LI> For all pairs of elements <IMG WIDTH=95 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68921" SRC="img1976.gif" >, <em>exactly one</em> of the following is true: <I>i</I><I><</I><I>j</I>, <I>i</I>=<I>j</I>, or <I>j</I><I><</I><I>i</I>.<P> (All elements are commensurate<A NAME=34351> </A>).<LI> For all triples <IMG WIDTH=142 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68929" SRC="img1977.gif" >, <IMG WIDTH=163 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61303" SRC="img799.gif" >.<P> (The relation <I><</I> is transitive<A NAME=34352> </A>).</OL></BLOCKQUOTE><P>In order to <em>sort</em> the elements of the sequence <I>S</I>,we determine the <em>permutation</em> <IMG WIDTH=160 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68937" SRC="img1978.gif" >of the elements of <I>S</I> such that<P> <IMG WIDTH=345 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath68895" SRC="img1979.gif" ><P>In practice, we are not interested in the permutation <I>P</I>, <em>per se</em>.Instead, our objective is to compute the sorted sequence <IMG WIDTH=160 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline68943" SRC="img1980.gif" >in which <IMG WIDTH=50 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68945" SRC="img1981.gif" > for <IMG WIDTH=64 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68947" SRC="img1982.gif" >.<P>Sometimes the sequence to be sorted, <I>S</I>, contains duplicates.That is, there exist values <I>i</I> and <I>j</I>, <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68955" SRC="img1983.gif" >, such that <IMG WIDTH=45 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline68957" SRC="img1984.gif" >.In general when a sequence that contains duplicates is sorted,there is no guarantee that the duplicated elementsretain their relative positions.That is, <IMG WIDTH=11 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68959" SRC="img1985.gif" > could appear either before or after <IMG WIDTH=11 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline68961" SRC="img1986.gif" >in the sorted sequence <I>S</I>'.If duplicates retain their relative positions in the sorted sequencethe sort is said to be <em>stable</em><A NAME=34364> </A>.In order for <IMG WIDTH=11 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68959" SRC="img1985.gif" > and <IMG WIDTH=11 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline68961" SRC="img1986.gif" > to retain their relative order in thesorted sequence,we require that <IMG WIDTH=16 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68969" SRC="img1987.gif" > precedes <IMG WIDTH=17 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68971" SRC="img1988.gif" > in <I>S</I>'.Therefore, the sort is stable if <IMG WIDTH=49 HEIGHT=19 ALIGN=MIDDLE ALT="tex2html_wrap_inline68975" SRC="img1989.gif" >.<P><HR><A NAME="tex2html6685" HREF="page480.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6683" HREF="page478.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6677" HREF="page478.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6687" 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 + =
减小字号Ctrl + -
显示快捷键?