📄 selection sort.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0055)http://linux.wku.edu/~lamonml/algor/sort/selection.html -->
<HTML><HEAD><TITLE>Selection 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 selection 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>Selection 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>The selection sort works by selecting the smallest unsorted
item remaining in the list, and then swapping it with the item in the next
position to be filled. The selection sort has a complexity of
<I>O</I>(<I>n</I><SUP>2</SUP>).
<P class=BodyText><B>Pros:</B> Simple and easy to implement.<BR><B>Cons:</B>
Inefficient for large lists, so similar to the more efficient <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/insertion.html">insertion</A>
sort that the insertion sort should be used in its place.
<P class=BodyText><FONT class=SectionText><B>Empirical Analysis</B></FONT><BR>
<CENTER><I class=BodyText>Selection Sort Efficiency</I><BR><IMG
alt="Selection Sort Efficiency Graph" src="Selection Sort_files/selection.jpg">
</CENTER>
<P class=BodyText>The selection sort is the unwanted stepchild of the
<I>n</I><SUP>2</SUP> sorts. It yields a 60% performance improvement over the <A
class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/bubble.html">bubble</A> sort, but
the <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/insertion.html">insertion</A>
sort is over twice as fast as the bubble sort and is just as easy to implement
as the selection sort. In short, there really isn't any reason to use the
selection sort - use the insertion sort instead.
<P class=BodyText>If you really want to use the selection sort for some reason,
try to avoid sorting lists of more than a 1000 items with it or repetitively
sorting lists of more than a couple hundred items.
<P class=BodyText><FONT class=SectionText><B>Source Code</B></FONT><BR>Below is
the basic selection 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> selectionSort(<B>int</B> numbers[], <B>int</B> array_size)
{
<B>int</B> i, j;
<B>int</B> min, temp;
<B>for</B> (i = 0; i < array_size-1; i++)
{
min = i;
<B>for</B> (j = i+1; j < array_size; j++)
{
<B>if</B> (numbers[j] < numbers[min])
min = j;
}
temp = numbers[i];
numbers[i] = numbers[min];
numbers[min] = temp;
}
}
</PRE></FONT></TD></TR></TBODY></TABLE></CENTER>
<P class=BodyText>A sample C program that demonstrates the use of the selection
sort may be <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/selection.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 + -