📄 bubble sort.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0052)http://linux.wku.edu/~lamonml/algor/sort/bubble.html -->
<HTML><HEAD><TITLE>Bubble 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 bubble 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>Bubble 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 bubble sort is the oldest and simplest sort in use.
Unfortunately, it's also the slowest.
<P class=BodyText>The bubble sort works by comparing each item in the list with
the item next to it, and swapping them if required. The algorithm repeats this
process until it makes a pass all the way through the list without swapping any
items (in other words, all items are in the correct order). This causes larger
values to "bubble" to the end of the list while smaller values "sink" towards
the beginning of the list.
<P class=BodyText>The bubble sort is generally considered to be the most
inefficient sorting algorithm in common usage. Under best-case conditions (the
list is already sorted), the bubble sort can approach a constant
<I>O</I>(<I>n</I>) level of complexity. General-case is an abysmal
<I>O</I>(<I>n</I><SUP>2</SUP>).
<P class=BodyText>While the <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/insertion.html">insertion</A>, <A
class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/selection.html">selection</A>,
and <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/shell.html">shell</A> sorts also
have <I>O</I>(<I>n</I><SUP>2</SUP>) complexities, they are significantly more
efficient than the bubble sort.
<P class=BodyText><B>Pros:</B> Simplicity and ease of
implementation.<BR><B>Cons:</B> Horribly inefficient.
<P class=BodyText><FONT class=SectionText><B>Empirical Analysis</B></FONT><BR>
<CENTER><I class=BodyText>Bubble Sort Efficiency</I><BR><IMG
alt="Bubble Sort Efficiency Graph" src="Bubble Sort_files/bubble.jpg"> </CENTER>
<P class=BodyText>The graph clearly shows the <I>n</I><SUP>2</SUP> nature of the
bubble sort.
<P class=BodyText>A fair number of algorithm purists (which means they've
probably never written software for a living) claim that the bubble sort should
never be used for any reason. Realistically, there isn't a noticeable
performance difference between the various sorts for 100 items or less, and the
simplicity of the bubble sort makes it attractive. The bubble sort shouldn't be
used for repetitive sorts or sorts of more than a couple hundred items.
<P class=BodyText><FONT class=SectionText><B>Source Code</B></FONT><BR>Below is
the basic bubble 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> bubbleSort(<B>int</B> numbers[], <B>int</B> array_size)
{
<B>int</B> i, j, temp;
<B>for</B> (i = (array_size - 1); i >= 0; i--)
{
<B>for</B> (j = 1; j <= i; j++)
{
<B>if</B> (numbers[j-1] > numbers[j])
{
temp = numbers[j-1];
numbers[j-1] = numbers[j];
numbers[j] = temp;
}
}
}
}
</PRE></FONT></TD></TR></TBODY></TABLE></CENTER>
<P class=BodyText>A sample C program that demonstrates the use of the bubble
sort may be <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/bubble.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 + -