📄 shell sort.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0051)http://linux.wku.edu/~lamonml/algor/sort/shell.html -->
<HTML><HEAD><TITLE>Shell Sort</TITLE>
<META content="text/html; charset=iso-8859-1" http-equiv=Content-Type>
<META content="Michael Lamont" name=Author>
<META
content="Description, source code, algorithm analysis, and empirical results for shell sort."
name=Description>
<STYLE type=text/css>.BlueLink {
COLOR: #0000ff; FONT-FAMILY: verdana,arial,helvetica; FONT-SIZE: 10pt; TEXT-DECORATION: none
}
A.BlueLink:hover {
COLOR: #0000ff; TEXT-DECORATION: underline
}
.TitleText {
COLOR: #000000; FONT-FAMILY: verdana,arial,helvetica; FONT-SIZE: 24pt; TEXT-DECORATION: none
}
.HeadText {
COLOR: #000000; FONT-FAMILY: verdana,arial,helvetica; FONT-SIZE: 18pt; TEXT-DECORATION: none
}
.BodyText {
COLOR: #000000; FONT-FAMILY: verdana,arial,helvetica; FONT-SIZE: 10pt; TEXT-DECORATION: none
}
.SectionText {
FONT-FAMILY: verdana,arial,helvetica; FONT-SIZE: 14pt
}
.ComText {
FONT-FAMILY: courier,fixed; FONT-SIZE: 10pt
}
</STYLE>
<META content="MSHTML 5.00.3700.6699" name=GENERATOR></HEAD>
<BODY><A class=BlueLink href="http://linux.wku.edu/~lamonml/kb.html">Knowledge
Base</A> > <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/">Algorithms & Data Structures</A>
> <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/index.html">Sorting
Algorithms</A>
<P><B class=TitleText>Shell Sort</B>
<HR align=left noShade SIZE=1 width="40%">
<P></P>
<P class=BodyText><FONT class=SectionText><B>Algorithm Analysis</B></FONT><BR>
<P class=BodyText>Invented by Donald Shell in 1959, the shell sort is the most
efficient of the <I>O</I>(<I>n</I><SUP>2</SUP>) class of sorting algorithms. Of
course, the shell sort is also the most complex of the
<I>O</I>(<I>n</I><SUP>2</SUP>) algorithms.
<P class=BodyText>The shell sort is a "diminishing increment sort", better known
as a "comb sort" to the unwashed programming masses. The algorithm makes
multiple passes through the list, and each time sorts a number of equally sized
sets using the insertion sort. The size of the set to be sorted gets larger with
each pass through the list, until the set consists of the entire list. (Note
that as the size of the set increases, the number of sets to be sorted
decreases.) This sets the <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/insertion.html">insertion</A>
sort up for an almost-best case run each iteration with a complexity that
approaches <I>O</I>(<I>n</I>).
<P class=BodyText>The items contained in each set are not contiguous - rather,
if there are <I>i</I> sets then a set is composed of every <I>i</I>-th element.
For example, if there are 3 sets then the first set would contain the elements
located at positions 1, 4, 7 and so on. The second set would contain the
elements located at positions 2, 5, 8, and so on; while the third set would
contain the items located at positions 3, 6, 9, and so on.
<P class=BodyText>The size of the sets used for each iteration has a major
impact on the efficiency of the sort. Several Heroes Of Computer
Science<SUP>TM</SUP>, including Donald Knuth and Robert Sedgewick, have come up
with more complicated versions of the shell sort that improve efficiency by
carefully calculating the best sized sets to use for a given list.
<P class=BodyText><B>Pros:</B> Efficient for medium-size lists.<BR><B>Cons:</B>
Somewhat complex algorithm, not nearly as efficient as the <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/merge.html">merge</A>, <A
class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/heap.html">heap</A>, and <A
class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/quick.html">quick</A> sorts.
<P class=BodyText><FONT class=SectionText><B>Empirical Analysis</B></FONT><BR>
<CENTER><I class=BodyText>Shell Sort Efficiency</I><BR><IMG
alt="Shell Sort Efficiency Graph" src="Shell Sort_files/shell.jpg"> </CENTER>
<P class=BodyText>The shell sort is by far the fastest of the
<I>N</I><SUP>2</SUP> class of sorting algorithms. It's more than 5 times faster
than the <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/bubble.html">bubble</A> sort and
a little over twice as fast as the <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/insertion.html">insertion</A>
sort, its closest competitor.
<P class=BodyText>The shell sort is still significantly slower than the <A
class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/merge.html">merge</A>, <A
class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/heap.html">heap</A>, and <A
class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/quick.html">quick</A> sorts, but
its relatively simple algorithm makes it a good choice for sorting lists of less
than 5000 items unless speed is hyper-critical. It's also an excellent choice
for repetitive sorting of smaller lists.
<P class=BodyText><FONT class=SectionText><B>Source Code</B></FONT><BR>Below is
the basic shell sort algorithm.
<P>
<CENTER>
<TABLE bgColor=#eeeeee border=0 cellSpacing=10 class=ComText width="90%">
<TBODY>
<TR>
<TD><FONT class=ComText><PRE><B>void</B> shellSort(<B>int</B> numbers[], <B>int</B> array_size)
{
<B>int</B> i, j, increment, temp;
increment = 3;
<B>while</B> (increment > 0)
{
<B>for</B> (i=0; i < array_size; i++)
{
j = i;
temp = numbers[i];
<B>while</B> ((j >= increment) && (numbers[j-increment] > temp))
{
numbers[j] = numbers[j - increment];
j = j - increment;
}
numbers[j] = temp;
}
<B>if</B> (increment/2 != 0)
increment = increment/2;
<B>else if</B> (increment == 1)
increment = 0;
<B>else</B>
increment = 1;
}
}
</PRE></FONT></TD></TR></TBODY></TABLE></CENTER>
<P class=BodyText>A sample C program that demonstrates the use of the shell sort
may be <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/shell.c">downloaded here</A>.
</P>
<HR align=center noShade SIZE=1 width="100%">
<A class=BlueLink href="http://linux.wku.edu/~lamonml/">Michael's
Homepage</A> <A class=BlueLink
href="http://linux.wku.edu/">WKU-Linux</A> </BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -