📄 insertion sort.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0055)http://linux.wku.edu/~lamonml/algor/sort/insertion.html -->
<HTML><HEAD><TITLE>Insertion 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 insertion 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>Insertion Sort</B>
<HR align=left noShade SIZE=1 width="40%">
<P></P>
<P class=BodyText><FONT class=SectionText><B>Algorithm
Analysis</B></FONT><BR>The insertion sort works just like its name suggests - it
inserts each item into its proper place in the final list. The simplest
implementation of this requires two list structures - the source list and the
list into which sorted items are inserted. To save memory, most implementations
use an in-place sort that works by moving the current item past the already
sorted items and repeatedly swapping it with the preceding item until it is in
place.
<P class=BodyText>Like the <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/bubble.html">bubble</A> sort, the
insertion sort has a complexity of <I>O</I>(<I>n</I><SUP>2</SUP>). Although it
has the same complexity, the insertion sort is a little over twice as efficient
as the bubble sort.
<P class=BodyText><B>Pros:</B> Relatively simple and easy to
implement.<BR><B>Cons:</B> Inefficient for large lists.
<P class=BodyText><FONT class=SectionText><B>Empirical Analysis</B></FONT><BR>
<CENTER><I class=BodyText>Insertion Sort Efficiency</I><BR><IMG
alt="Insertion Sort Efficiency Graph" src="Insertion Sort_files/insertion.jpg">
</CENTER>
<P class=BodyText>The graph demonstrates the <I>n</I><SUP>2</SUP> complexity of
the insertion sort.
<P class=BodyText>The insertion sort is a good middle-of-the-road choice for
sorting lists of a few thousand items or less. The algorithm is significantly
simpler than the <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/shell.html">shell</A> sort, with
only a small trade-off in efficiency. At the same time, the insertion sort is
over twice as fast as the <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/bubble.html">bubble</A> sort and
almost 40% faster than the <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/selection.html">selection</A>
sort. The insertion sort shouldn't be used for sorting lists larger than a
couple thousand items or repetitive sorting of lists larger than a couple
hundred items.
<P class=BodyText><FONT class=SectionText><B>Source Code</B></FONT><BR>Below is
the basic insertion 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> insertionSort(<B>int</B> numbers[], <B>int</B> array_size)
{
<B>int</B> i, j, index;
<B>for</B> (i=1; i < array_size; i++)
{
index = numbers[i];
j = i;
<B>while</B> ((j > 0) && (numbers[j-1] > index))
{
numbers[j] = numbers[j-1];
j = j - 1;
}
numbers[j] = index;
}
}
</PRE></FONT></TD></TR></TBODY></TABLE></CENTER>
<P class=BodyText>A sample C program that demonstrates the use of the insertion
sort may be <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/insertion.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 + -