📄 quick sort.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0051)http://linux.wku.edu/~lamonml/algor/sort/quick.html -->
<HTML><HEAD><TITLE>Quick 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 quick 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>Quick 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 quick sort is an in-place, divide-and-conquer, massively
recursive sort. As a normal person would say, it's essentially a faster in-place
version of the merge sort. The quick sort algorithm is simple in theory, but
very difficult to put into code (computer scientists tied themselves into knots
for years trying to write a practical implementation of the algorithm, and it
still has that effect on university students).
<P class=BodyText>The recursive algorithm consists of four steps (which closely
resemble the merge sort):
<OL class=BodyText>
<LI>If there are one or less elements in the array to be sorted, return
immediately.
<LI>Pick an element in the array to serve as a "pivot" point. (Usually the
left-most element in the array is used.)
<LI>Split the array into two parts - one with elements larger than the pivot
and the other with elements smaller than the pivot.
<LI>Recursively repeat the algorithm for both halves of the original array.
</LI></OL>
<P class=BodyText>The efficiency of the algorithm is majorly impacted by which
element is choosen as the pivot point. The worst-case efficiency of the quick
sort, <I>O</I>(<I>n</I><SUP>2</SUP>), occurs when the list is sorted and the
left-most element is chosen. Randomly choosing a pivot point rather than using
the left-most element is recommended if the data to be sorted isn't random. As
long as the pivot point is chosen randomly, the quick sort has an algorithmic
complexity of <I>O</I>(<I>n</I> log <I>n</I>).
<P class=BodyText><B>Pros:</B> Extremely fast.<BR><B>Cons:</B> Very complex
algorithm, massively recursive.
<P class=BodyText><FONT class=SectionText><B>Empirical Analysis</B></FONT><BR>
<CENTER><I class=BodyText>Quick Sort Efficiency</I><BR><IMG
alt="Quick Sort Efficiency Graph" src="Quick Sort_files/quick.jpg"> </CENTER>
<P class=BodyText>The quick sort is by far the fastest of the common sorting
algorithms. It's possible to write a special-purpose sorting algorithm that can
beat the quick sort for some data sets, but for general-case sorting there isn't
anything faster.
<P class=BodyText>As soon as students figure this out, their immediate implulse
is to use the quick sort for everything - after all, faster is better, right?
It's important to resist this urge - the quick sort isn't always the best
choice. As mentioned earlier, it's massively recursive (which means that for
very large sorts, you can run the system out of stack space pretty easily). It's
also a complex algorithm - a little too complex to make it practical for a
one-time sort of 25 items, for example.
<P class=BodyText>With that said, in most cases the quick sort is the best
choice if speed is important (and it almost always is). Use it for repetitive
sorting, sorting of medium to large lists, and as a default choice when you're
not really sure which sorting algorithm to use. Ironically, the quick sort has
horrible efficiency when operating on lists that are mostly sorted in either
forward or reverse order - avoid it in those situations.
<P class=BodyText><FONT class=SectionText><B>Source Code</B></FONT><BR>Below is
the basic quick 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> quickSort(<B>int</B> numbers[], <B>int</B> array_size)
{
q_sort(numbers, 0, array_size - 1);
}
<B>void</B> q_sort(<B>int</B> numbers[], <B>int</B> left, <B>int</B> right)
{
<B>int</B> pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers[left];
<B>while</B> (left < right)
{
<B>while</B> ((numbers[right] >= pivot) && (left < right))
right--;
<B>if</B> (left != right)
{
numbers[left] = numbers[right];
left++;
}
<B>while</B> ((numbers[left] <= pivot) && (left < right))
left++;
<B>if</B> (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
<B>if</B> (left < pivot)
q_sort(numbers, left, pivot-1);
<B>if</B> (right > pivot)
q_sort(numbers, pivot+1, right);
}
</PRE></FONT></TD></TR></TBODY></TABLE></CENTER>
<P class=BodyText>A sample C program that demonstrates the use of the quick sort
may be <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/quick.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 + -