page514.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 141 行
HTML
141 行
<HTML><HEAD><TITLE>Radix Sort</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="tex2html7072" HREF="page515.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7070" HREF="page511.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7066" HREF="page513.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7074" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0015820000000000000000">Radix Sort</A></H2><A NAME="secsortingradix"> </A><P>This section presents a sorting algorithm known as<em>least-significant-digit-first radix sorting</em><A NAME=45413> </A><A NAME=45414> </A>.Radix sorting is based on the bucket sorting algorithm discussedin the preceding section.However, radix sorting is practical for much larger universal setsthan it is practical to handle with a bucket sort.<P>Radix sorting can be used when each element of the universal setcan be viewed as a sequences of digits (or letters or any other symbols).For example, we can represent each integer between 0 and 99as a sequence of two, decimal digits.(For example, the number five is represented as ``05'').<P>To sort an array of two-digit numbers,the algorithm makes two sorting passes through the array.In the first pass,the elements of the array are sorted by the<em>least significant</em> decimal digit.In the second pass,the elements of the array are sorted by the<em>most significant</em> decimal digit.The key characteristic of the radix sort is that the second passis done in such a way that it does not destroy the effectof the first pass.Consequently, after two passes through the array,the data is contained therein is sorted.<P>Each pass of the radix sort is implemented as a bucket sort.In the example we base the sort on <em>decimal</em> digits.Therefore, this is called a <em>radix-10</em> sortand ten buckets are required to do each sorting pass.<P>Figure <A HREF="page514.html#figsort9"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates the operation of the radix-10 sort.The first radix sorting pass considers the least significant digits.As in the bucket sort, a single pass is made through the unsorted data,counting the number of times each decimal digit appearsas the least-significant digit.For example, there are no elements that have a 0 as the least-significant digit;there are two elements that have a 1 as the least-significant digit; and so on.<P><P><A NAME="46242"> </A><A NAME="figsort9"> </A> <IMG WIDTH=575 HEIGHT=443 ALIGN=BOTTOM ALT="figure45420" SRC="img2109.gif" ><BR><STRONG>Figure:</STRONG> Radix sorting.<BR><P><P>After the counts have been determined,it is necessary to permute the input sequence so that it is sortedby the least-significant digits.To do this permutation efficiently,we compute the sequence of <em>offsets</em> given by<P><A NAME="eqnsortingx"> </A> <IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation46246" SRC="img2110.gif" ><P>where <I>R</I> is the sorting radix.Note that <IMG WIDTH=63 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69821" SRC="img2111.gif" > is the position in the permuted sequenceof the first occurrence of an element whose least significant digit is <I>i</I>.By making use of the offsets,it is possible to permute the input sequence by making a single passthrough the sequence.<P>The second radix sorting pass considers the most significant digits.As above a single pass is made through the permuted data sequencecounting the number of times each decimal digit appearsas the most-significant digit.Then the sequence of <em>offsets</em> is computed as above.The sequence is permuted again using the offsetsproducing the final, sorted sequence.<P>In general, radix sorting can be used when the elements of theuniverse can be viewed as <I>p</I>-digit numbers with respect to some radix, <I>R</I>.That is, each element of the universe has the form<P> <IMG WIDTH=280 HEIGHT=47 ALIGN=BOTTOM ALT="displaymath69809" SRC="img2112.gif" ><P>where <IMG WIDTH=146 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69829" SRC="img2113.gif" > for <IMG WIDTH=64 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline69831" SRC="img2114.gif" >.In this case, the radix sort algorithm must make <I>p</I> sorting passesfrom the least significant digit, <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline69835" SRC="img2115.gif" >,to the most significant digit, <IMG WIDTH=30 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline69837" SRC="img2116.gif" >,and each sorting pass uses exactly <I>R</I> counters.<P>Radix sorting can also be used when the universe can be viewedas the cross-product of a finite number of finite sets.That is, when the universe has the form<P> <IMG WIDTH=353 HEIGHT=15 ALIGN=BOTTOM ALT="displaymath69810" SRC="img2117.gif" ><P>where <I>p</I><I>></I>0 is a fixed integer constant and <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68643" SRC="img1925.gif" > is a finite set for <IMG WIDTH=63 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline69845" SRC="img2118.gif" >.For example, each card in a 52-card deck of playing cardscan be represented as an element of <IMG WIDTH=88 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline69847" SRC="img2119.gif" >, where <IMG WIDTH=124 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69849" SRC="img2120.gif" >and <IMG WIDTH=267 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69851" SRC="img2121.gif" >.<P>Before we can sort over the universe <I>U</I>,we need to define what it means for one element to precede another in <I>U</I>.The usual way to do this is called<em>lexicographic ordering</em><A NAME=46261> </A>.For example in the case of the playing cards we may say thatone card precedes another if its suit precedes the other suitor if the suits are equal but the face value precedes that of the other.<P>In general, given the universe <IMG WIDTH=200 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline69857" SRC="img2122.gif" >,and two elements of <I>U</I>, say <I>x</I> and <I>y</I>,represented by the <I>p</I>-tuples <IMG WIDTH=133 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69867" SRC="img2123.gif" > and <IMG WIDTH=128 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69869" SRC="img2124.gif" >, respectively,we say that <I>x</I> <em>lexicographically precedes</em><A NAME=46263> </A><A NAME=46264> </A> <I>y</I>if there exists <IMG WIDTH=67 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline69875" SRC="img2125.gif" > such that <IMG WIDTH=52 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline69877" SRC="img2126.gif" > and <IMG WIDTH=48 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline69879" SRC="img2127.gif" > for all <IMG WIDTH=63 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69881" SRC="img2128.gif" >.<P>With this definition of precedence,we can radix sort a sequence of elements drawn from <I>U</I>by sorting with respect to the components of the <I>p</I>-tuples.Specifically, we sort first with respect to <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline69887" SRC="img2129.gif" >, then <IMG WIDTH=31 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline69889" SRC="img2130.gif" >,and so on down to <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline69891" SRC="img2131.gif" >.Notice that the algorithm does <I>p</I> sorting passesand in the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > pass it requires <IMG WIDTH=23 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69897" SRC="img2132.gif" > counters.For example to sort a deck of cards,two passes are required.In first pass the cards are sorted into 13 pilesaccording to their face values.In the second pass the cards are sorted into four pilesaccording to their suits.<P><BR> <HR><UL> <LI> <A NAME="tex2html7075" HREF="page515.html#SECTION0015821000000000000000">Implementation</A></UL><HR><A NAME="tex2html7072" HREF="page515.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7070" HREF="page511.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7066" HREF="page513.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7074" 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 + -
显示快捷键?