page451.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 63 行
HTML
63 行
<HTML><HEAD><TITLE>Example-Merge 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="tex2html6366" HREF="page452.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6364" HREF="page448.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6358" HREF="page450.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6368" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0014330000000000000000">Example-Merge Sorting</A></H2><A NAME="secalgsmergesort"> </A><P>Sorting algorithms and sorters are covered in detail in Chapter <A HREF="page478.html#chapsorting"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.In this section we consider a divide-and-conquer sorting algorithm--<em>merge sort</em><A NAME=32765> </A>.Given an array of <I>n</I> items in arbitrary order,the objective is to rearrange the elements of the arrayso that they are ordered from the smallest element to the largest one.<P>The merge sort algorithm sorts a sequence of length <I>n</I><I>></I>1by splitting it into to subsequences--one of length <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58273" SRC="img177.gif" >,the other of length <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67953" SRC="img1774.gif" >.Each subsequence is sorted and then the two sorted sequencesare merged into one.<P>Program <A HREF="page451.html#progexampleq"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the method <tt>mergeSort</tt> whichtakes three arguments,<tt>array</tt>, <tt>i</tt>, and <tt>n</tt>.The method sorts the following <tt>n</tt> elements:<P> <IMG WIDTH=448 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath67879" SRC="img1757.gif" ><P>The <tt>mergeSort</tt> method calls itselfas well as the <tt>merge</tt> method.The purpose of the <tt>merge</tt> method is to merge two sorted sequences,one of length <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58273" SRC="img177.gif" >,the other of length <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67953" SRC="img1774.gif" >,into a single sorted sequence of length <I>n</I>.This can easily be done in <I>O</I>(<I>n</I>) time.(See Program <A HREF="page507.html#progtwoWayMergeSorterb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).<P><P><A NAME="32788"> </A><A NAME="progexampleq"> </A> <IMG WIDTH=575 HEIGHT=107 ALIGN=BOTTOM ALT="program32785" SRC="img1775.gif" ><BR><STRONG>Program:</STRONG> Divide-and-conquer example--merge sorting.<BR><P><P>The running time of the <tt>mergeSort</tt> methoddepends on the number of items to be sorted, <I>n</I>.Although Program <A HREF="page451.html#progexampleq"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> works correctly for arbitrary values of <I>n</I>,it is much easier to determine the running timeif we assume that <I>n</I> is a power of two.In this case,the running time is given by the recurrence<P><A NAME="eqnalgsms"> </A> <IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation32794" SRC="img1776.gif" ><P><P>Equation <A HREF="page451.html#eqnalgsms"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is easily solved using repeated substitution:<P> <IMG WIDTH=500 HEIGHT=122 ALIGN=BOTTOM ALT="eqnarray32800" SRC="img1777.gif" ><P>Setting <IMG WIDTH=62 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline67909" SRC="img1761.gif" > gives <IMG WIDTH=219 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67971" SRC="img1778.gif" >.<P><HR><A NAME="tex2html6366" HREF="page452.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6364" HREF="page448.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6358" HREF="page450.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6368" 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 + -
显示快捷键?