📄 page483.html
字号:
<HTML><HEAD><TITLE>Insertion Sorting</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="tex2html6729" HREF="page484.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6727" HREF="page478.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6721" HREF="page482.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6731" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0015300000000000000000">Insertion Sorting</A></H1><P>The first class of sorting algorithm that we considercomprises algorithms that <em>sort by insertion</em><A NAME=34428> </A><A NAME=34429> </A>.An algorithm that sorts by insertion takes the initial,unsorted sequence, <IMG WIDTH=156 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68897" SRC="img1975.gif" >,and computes a series of <em>sorted</em> sequences <IMG WIDTH=117 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68981" SRC="img1992.gif" >,as follows:<OL><LI> The first sequence in the series, <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68983" SRC="img1993.gif" > is the empty sequence. That is, <IMG WIDTH=52 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline68985" SRC="img1994.gif" >.<LI> Given a sequence <IMG WIDTH=13 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68987" SRC="img1995.gif" > in the series, for <IMG WIDTH=65 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62043" SRC="img895.gif" >, the next sequence in the series, <IMG WIDTH=28 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline68991" SRC="img1996.gif" >, is obtained by inserting the <IMG WIDTH=56 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline62863" SRC="img1058.gif" > element of the unsorted sequence <IMG WIDTH=26 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline68995" SRC="img1997.gif" > into the correct position in <IMG WIDTH=13 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68987" SRC="img1995.gif" >.</OL>Each sequence <IMG WIDTH=13 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68987" SRC="img1995.gif" >, <IMG WIDTH=65 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62043" SRC="img895.gif" >,contains the first <I>i</I> elements of the unsorted sequence <I>S</I>.Therefore, the final sequence in the series, <IMG WIDTH=17 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline69007" SRC="img1998.gif" >,is the sorted sequence we seek. That is, <IMG WIDTH=54 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline69009" SRC="img1999.gif" >.<P>Figure <A HREF="page483.html#figsort1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates the insertion sorting algorithm.The figure shows the progression of the insertion sorting algorithmas it sorts an array of ten integers.The array is sorted<em>in place</em><A NAME=34438> </A><A NAME=34439> </A>.That is, the initial unsorted sequence, <I>S</I>,and the series of sorted sequences, <IMG WIDTH=64 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline69013" SRC="img2000.gif" >,occupy the same array.<P><P><A NAME="35061"> </A><A NAME="figsort1"> </A> <IMG WIDTH=575 HEIGHT=600 ALIGN=BOTTOM ALT="figure34440" SRC="img2001.gif" ><BR><STRONG>Figure:</STRONG> Insertion sorting.<BR><P><P>In the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > step,the element at position <I>i</I> in the array is inserted into thesorted sequence <IMG WIDTH=13 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68987" SRC="img1995.gif" > which occupies array positions 0 to (<I>i</I>-1).After this is done,array positions 0 to <I>i</I> contain the <I>i</I>+1 elements of <IMG WIDTH=28 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline68991" SRC="img1996.gif" >.Array positions (<I>i</I>+1) to (<I>n</I>-1) containthe remaining <I>n</I>-<I>i</I>-1 elements of the unsorted sequence <I>S</I>.<P>As shown in Figure <A HREF="page483.html#figsort1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the first step (<I>i</I>=0) is trivial--inserting an element into the empty list involves no work.Altogether, <I>n</I>-1 non-trivial insertions are requiredto sort a list of <I>n</I> elements.<P><BR> <HR><UL> <LI> <A NAME="tex2html6732" HREF="page484.html#SECTION0015310000000000000000">Straight Insertion Sort</A><LI> <A NAME="tex2html6733" HREF="page486.html#SECTION0015320000000000000000">Average Running Time</A><LI> <A NAME="tex2html6734" HREF="page487.html#SECTION0015330000000000000000">Binary Insertion Sort</A></UL><HR><A NAME="tex2html6729" HREF="page484.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6727" HREF="page478.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6721" HREF="page482.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6731" 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 + -