s_shl.htm
来自「Data Structure Ebook」· HTM 代码 · 共 99 行
HTM
99 行
<html>
<head>
<title>Shell Sort</title>
</head>
<body bgcolor="#ffffff">
<p align=right>
<a href="s_man.htm" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_man.htm" target="_top"><img src="c_man.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/c_man.gif" width=74 height=19 border=0></a>
</p>
<h1>Shell Sort</h1>
Shell sort, developed by Donald L. Shell, is a non-stable
in-place sort. Shell sort improves on the efficiency of insertion
sort by <i>quickly</i> shifting values to their destination. Average
sort time is <b><i>O</i></b>(<i>n</i><sup>1.25</sup>),
while worst-case time is <b><i>O</i></b>(<i>n</i><sup>1.5</sup>). For
further reading, consult
<a href="javascript:if(confirm('http://www.amazon.com/exec/obidos/ISBN=0201896850/none01A/ \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.amazon.com/exec/obidos/ISBN=0201896850/none01A/'" tppabs="http://www.amazon.com/exec/obidos/ISBN=0201896850/none01A/" target="_top">Knuth [1998]</a>.
<h2>Theory</h2>
In
Figure 2-2(a) we have an example of sorting by insertion.
First we extract 1, shift 3 and 5 down one slot, and then insert
the 1, for a count of 2 shifts. In the next frame, two
shifts are required before we can insert the 2. The process
continues until the last frame, where a total of 2 + 2 + 1 = 5
shifts have been made.
<p>
In Figure 2-2(b)
an example of shell sort is illustrated. We
begin by doing an insertion sort using a <i>spacing</i> of two. In the
first frame we examine numbers 3-1. Extracting 1, we shift 3
down one slot for a shift count of 1. Next we examine numbers
5-2. We extract 2, shift 5 down, and then insert 2. After sorting
with a spacing of two, a final pass is made with a spacing of
one. This is simply the traditional insertion sort. The total
shift count using shell sort is 1+1+1 = 3. By using an initial
spacing larger than one, we were able to quickly shift values to
their proper destination.
<p>
<center>
<h3><a name="Fig2-2">
<img src="s_fig22.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_fig22.gif" vspace=5 width=559 height=294><br>
Figure 2-2: Shell Sort</a>
</h3>
</center>
<p>
Various spacings may be used to implement a shell sort.
Typically the array is sorted with a large spacing, the spacing
reduced, and the array sorted again. On the final sort, spacing
is one. Although the shell sort is easy to comprehend, formal
analysis is difficult. In particular, optimal spacing values
elude theoreticians. Knuth
has experimented with several
values and recommends that spacing <i>h</i> for an array of size <i>N</i> be
based on the following formula:
<p>
<center>
<i>Let h</i><sub>1</sub> = 1, <i>h</i><sub>s+1</sub> = 3<i>h</i><sub>s</sub> + 1,
<i>and stop with h</i><sub>t</sub> <i> when h</i><sub>t+2</sub> >= <i>N</i>.
</center>
<p>
Thus, values of <i>h</i> are computed as follows:
<blockquote>
<i>h</i><sub>1</sub> = 1<br>
<i>h</i><sub>2</sub> = (3 x 1) + 1 = 4<br>
<i>h</i><sub>3</sub> = (3 x 4) + 1 = 13<br>
<i>h</i><sub>4</sub> = (3 x 13) + 1 = 40<br>
<i>h</i><sub>5</sub> = (3 x 40) + 1 = 121<br>
</blockquote>
To sort 100 items we first find an <i>h</i><sub>s</sub>
such that <i>h</i><sub>s</sub> >= 100.
For 100 items, <i>h</i><sub>5</sub> is selected.
Our final value (<i>h</i><sub>t</sub>) is two steps lower,
or <i>h</i><sub>3</sub>. Therefore our sequence of <i>h</i> values will be 13-4-1. Once the
initial <i>h</i> value has been determined, subsequent values may be
calculated using the formula
<p>
<center>
<i>h</i><sub>s-1</sub> = <i>floor</i>(<i>h</i><sub>s</sub> / 3).
</center>
<h2>Implementation</h2>
An
<a href="javascript:if(confirm('http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_shl.txt \n\nThis file was not retrieved by Teleport Pro, because it is linked too far away from its Starting Address. If you increase the in-domain depth setting for the Starting Address, this file will be queued for retrieval. \n\nDo you want to open it from the server?'))window.location='http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_shl.txt'" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_shl.txt">ANSI-C implementation</a>
for shell sort is included.
<b>Typedef T</b> and comparison operator <b>compGT</b> should
be altered to reflect the data stored in the array.
The central portion of the algorithm is an insertion sort with a
spacing of <i>h</i>.
</body>
</html>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?