unshufflsort.html
来自「数据结构词典（英文）」· HTML 代码 · 共 48 行
HTML
48 行
<!DOCTYPE HTML PUBLIC "-//IETF//DTD W3 HTML 2.0//EN">
<HTML lang="en-US">
<HEAD>
<TITLE>UnShuffle sort</TITLE>
<META name="description"
content="Definition of UnShuffle sort,
possibly with links to more information and implementations.">
<META name="keywords" content="UnShuffle sort">
</HEAD>
<BODY BGCOLOR="#FFFFFF">
<H1>UnShuffle sort</H1>
<P>
(algorithm)
<P>
<strong>Definition:</strong>
A <a href="distribsort.html" tppabs="http://hissa.nist.gov/dads/HTML/distribsort.html"><em>distribution sort</em></a> with two phases. In the first phase, the inputs are distributed among <a href="deque.html" tppabs="http://hissa.nist.gov/dads/HTML/deque.html"><em>doubly-ended queues</em></a> keeping the items in each queue ordered and creating a new queue when there is no place on an existing queue. The second phase is an <a href="idealmerge.html" tppabs="http://hissa.nist.gov/dads/HTML/idealmerge.html"><em>ideal merge</em></a> in which the item to be removed is determined by keeping the queues in a <a href="priorityque.html" tppabs="http://hissa.nist.gov/dads/HTML/priorityque.html"><em>priority queue</em></a>.
<P><strong>See also</strong>
<a href="mergesort.html" tppabs="http://hissa.nist.gov/dads/HTML/mergesort.html"><em>merge sort</em></a>, <a href="distribsort.html" tppabs="http://hissa.nist.gov/dads/HTML/distribsort.html"><em>distribution sort</em></a>, <a href="idealmerge.html" tppabs="http://hissa.nist.gov/dads/HTML/idealmerge.html"><em>ideal merge</em></a>, <a href="pile.html" tppabs="http://hissa.nist.gov/dads/HTML/pile.html"><em>pile</em></a>.
<P><em>Note:
The doubly-ended queue with ordered items is called a <a href="pile.html" tppabs="http://hissa.nist.gov/dads/HTML/pile.html"><em>pile</em></a>. The UnShuffle algorithm is the most efficient available for sorting data streams that exhibit low entropy, i.e., are already mostly sorted or contains runs of sorted elements. The run time is <a href="theta.html" tppabs="http://hissa.nist.gov/dads/HTML/theta.html"><em> <img src="Theta-1.gif" tppabs="http://hissa.nist.gov/dads/HTML/Images/Theta.gif" border=0 height=10 width=8 alt="Capital Theta"></em></a>(N) for sorted input. The general case is <em>(K/2)*N + NlogK</em> where <em>K</em> is the entropy of the input and is manifest in the number of piles generated during the distribution phase. <P> First published in <strong>Art S. Kagel</strong>, <em>Unshuffle Algorithm, Not Quite a Sort?</em>, Computer Language Magazine, Vol. 3, No. 11, November 1985.</em>
<P>Author: <a href="terms.html#authorASK" tppabs="http://hissa.nist.gov/dads/terms.html#authorASK">ASK</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 Jun 7 13:46:39 1999.<BR>
HTML page formatted Wed Dec 22 09:36:50 1999.
<P>
This page's URL is
<A href="unshufflsort.html" tppabs="http://hissa.nist.gov/dads/HTML/unshufflsort.html">http://hissa.nist.gov/dads/HTML/unshufflsort.html</A>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?