📄 radixsort.html
字号:
<!DOCTYPE HTML PUBLIC "-//IETF//DTD W3 HTML 2.0//EN">
<HTML lang="en-US">
<HEAD>
<TITLE>radix sort</TITLE>
<META name="description"
content="Definition of radix sort,
possibly with links to more information and implementations.">
<META name="keywords" content="radix sort">
</HEAD>
<BODY BGCOLOR="#FFFFFF">
<H1>radix sort</H1>
<P>
(algorithm)
<P>
<strong>Definition:</strong>
A multiple pass <a href="sort.html" tppabs="http://hissa.nist.gov/dads/HTML/sort.html"><em>sort</em></a> algorithm that distributes each item to a <a href="bucket.html" tppabs="http://hissa.nist.gov/dads/HTML/bucket.html"><em>bucket</em></a> according to part of the item's <a href="key.html" tppabs="http://hissa.nist.gov/dads/HTML/key.html"><em>key</em></a> beginning with the least significant part of the key. After each pass, items are collected from the buckets, keeping the items in order, then redistributed according to the next most significant part of the key.
<P><strong>See also</strong>
<a href="bucketsort.html" tppabs="http://hissa.nist.gov/dads/HTML/bucketsort.html"><em>bucket sort</em></a>.
<P><em>Note:
This is the algorithm used by letter-sorting machines in the post office. Since keys are not compared against each other, sorting time is <a href="bigOnotation.html" tppabs="http://hissa.nist.gov/dads/HTML/bigOnotation.html"><em>O(cn)</em></a>, where <em>c</em> depends on the size of the key and number of buckets. You have probably used a form of this if you sorted lots of papers alphabetically: you put each paper in its pile (or bucket), A's, B's, C's, D's, etc., then sort each pile. <P> Here is a simple example of the sort. Suppose the input keys are 34, 12, 42, 32, 44, 41, 34, 11, 32, and 23. Let's use four buckets. The first pass distributes them by the least significant digit. After the first pass we have the following, where each line is a bucket.<BR> 41 11<BR> 12 42 32 32<BR> 23<BR> 34 44 34<BR> We collect these up, keeping their relative order: 41 11 12 42 32 32 23 34 44 34. Now we distribute by the next most significant digit, in this case, the highest digit, and we get the following.<BR> 11 12<BR> 23<BR> 32 32 34 34<BR> 41 42 44<BR> When we collect them up, they are in order: 11 12 23 32 32 34 34 41 42 44. <P> [CLR] gives an <a href="inplacesort.html" tppabs="http://hissa.nist.gov/dads/HTML/inplacesort.html"><em>in-place</em></a> variant of radix sort by using a <a href="stable.html" tppabs="http://hissa.nist.gov/dads/HTML/stable.html"><em>stable</em></a> sort on each digit of the key.</em>
<P>Author: <a href="terms.html#authorPEB" tppabs="http://hissa.nist.gov/dads/terms.html#authorPEB">PEB</a>
<H2>Implementation</H2>
<A HREF="javascript:if(confirm('http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.dcc.uchile.cl/%7Eoalonso/handbook/algs/4/424.sort.c.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://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.dcc.uchile.cl/%7Eoalonso/handbook/algs/4/424.sort.c.html'" tppabs="http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.dcc.uchile.cl/%7Eoalonso/handbook/algs/4/424.sort.c.html">(C and Pascal)</A>, <A HREF="javascript:if(confirm('http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.ee.uwa.edu.au/%7Eplsd210/ds/radixsort.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://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.ee.uwa.edu.au/%7Eplsd210/ds/radixsort.html'" tppabs="http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.ee.uwa.edu.au/%7Eplsd210/ds/radixsort.html">analysis, explanation, and code (C)</A>,<A HREF="javascript:if(confirm('http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.cubic.org/%7Esubmissive/sourcerer/radix.htm \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://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.cubic.org/%7Esubmissive/sourcerer/radix.htm'" tppabs="http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.cubic.org/%7Esubmissive/sourcerer/radix.htm">tutorial with examples and code (C++)</a>
<H2>More information</H2>
<A HREF="javascript:if(confirm('http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.math.grin.edu/%7Estone/courses/fundamentals/radix-sorting.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://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.math.grin.edu/%7Estone/courses/fundamentals/radix-sorting.html'" tppabs="http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.math.grin.edu/%7Estone/courses/fundamentals/radix-sorting.html">Radix sorting</A>
<hr>
Go to the
<A HREF="terms.html" tppabs="http://hissa.nist.gov/dads/terms.html">Algorithms, Data Structures, and Problems</A>
home page.
<hr>
If you have suggestions, corrections, or comments, please get in touch
with
<a href="javascript:if(confirm('http://hissa.nist.gov/~black/black.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://hissa.nist.gov/~black/black.html'" tppabs="http://hissa.nist.gov/~black/black.html">Paul E. Black</a>
(<a href="mailto:paul.black@nist.gov">paul.black@nist.gov</a>).
<p>
Entry modified Mon Nov 1 10:17:23 1999.<BR>
HTML page formatted Wed Dec 22 09:36:17 1999.
<P>
This page's URL is
<A href="radixsort.html" tppabs="http://hissa.nist.gov/dads/HTML/radixsort.html">http://hissa.nist.gov/dads/HTML/radixsort.html</A>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -