📄 tij0091.html
字号:
<html><body>
<table width="100%"><tr>
<td>
<a href="http://www.bruceeckel.com/javabook.html">Bruce Eckel's Thinking in Java</a>
</td>
<td align="right">
<a href="tij_c.html">Contents</a> | <a href="tij0090.html">Prev</a> | <a href="tij0092.html">Next</a>
</td>
</tr></table>
<hr>
<H2 ALIGN=LEFT>
Sorting</H2>
<DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">One
of the things missing in the Java 1.0<A NAME="Index812"></A>
and 1.1 libraries is algorithmic operations, even simple <A NAME="Index813"></A>sorting.
So it makes sense to create a
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Vector</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
that sorts itself using the classic <A NAME="Index814"></A>Quicksort.</FONT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">A
problem with writing generic sorting code is that sorting must perform
comparisons based on the actual type of the object. Of course, one approach is
to write a different sorting method for every different type, but you should be
able to recognize that this does not produce code that is easily re-used for
new types.
</FONT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">A
primary goal of programming design is to “separate things that change
from things that stay the same,” and here, the code that stays the same
is the general sort algorithm, but the thing that changes from one use to the
next is the way objects are compared. So instead of hard-wiring the comparison
code into many different sort routines, the technique of the <A NAME="Index815"></A></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><I>callback</I></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
will be used. With a callback, the part of the code that varies from case to
case is encapsulated inside its own class, and the part of the code
that’s always the same will call back to the code that changes. That way
you can make different objects to express different ways of comparison and feed
them to the same sorting code.
</FONT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">The
following
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>interface</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
describes how to compare two objects, and thus encapsulates “the things
that change” for this particular problem:
</FONT><P></DIV>
<font color="#990000"><PRE><font color="#009900">//: Compare.java</font>
<font color="#009900">// Interface for sorting callback:</font>
<font color="#0000ff">package</font> c08;
<font color="#0000ff">interface</font> Compare {
<font color="#0000ff">boolean</font> lessThan(Object lhs, Object rhs);
<font color="#0000ff">boolean</font> lessThanOrEqual(Object lhs, Object rhs);
} <font color="#009900">///:~ </PRE></font></font><DIV ALIGN=LEFT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">For
both methods, the
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>lhs</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
represents the “left hand” object and the
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>rhs</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
represents the “right hand” object in the comparison.
</FONT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">A
subclass of
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Vector</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
can be created that implements the Quicksort using
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Compare</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">.
The algorithm, which is known for its speed, will not be explained here. For
details, see
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><I>Practical
Algorithms for Programmers
</I></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">,
by Binstock & Rex, Addison-Wesley 1995.
</FONT><P></DIV>
<font color="#990000"><PRE><font color="#009900">//: SortVector.java</font>
<font color="#009900">// A generic sorting vector</font>
<font color="#0000ff">package</font> c08;
<font color="#0000ff">import</font> java.util.*;
<font color="#0000ff">public</font> <font color="#0000ff">class</font> SortVector <font color="#0000ff">extends</font> Vector {
<font color="#0000ff">private</font> Compare compare; <font color="#009900">// To hold the callback</font>
<font color="#0000ff">public</font> SortVector(Compare comp) {
compare = comp;
}
<font color="#0000ff">public</font> <font color="#0000ff">void</font> sort() {
quickSort(0, size() - 1);
}
<font color="#0000ff">private</font> <font color="#0000ff">void</font> quickSort(<font color="#0000ff">int</font> left, <font color="#0000ff">int</font> right) {
<font color="#0000ff">if</font>(right > left) {
Object o1 = elementAt(right);
<font color="#0000ff">int</font> i = left - 1;
<font color="#0000ff">int</font> j = right;
<font color="#0000ff">while</font>(<font color="#0000ff">true</font>) {
<font color="#0000ff">while</font>(compare.lessThan(
elementAt(++i), o1))
;
<font color="#0000ff">while</font>(j > 0)
<font color="#0000ff">if</font>(compare.lessThanOrEqual(
elementAt(--j), o1))
<font color="#0000ff">break</font>; <font color="#009900">// out of while</font>
<font color="#0000ff">if</font>(i >= j) <font color="#0000ff">break</font>;
swap(i, j);
}
swap(i , right);
quickSort(left, i-1);
quickSort(i+1, right);
}
}
<font color="#0000ff">private</font> <font color="#0000ff">void</font> swap(<font color="#0000ff">int</font> loc1, <font color="#0000ff">int</font> loc2) {
Object tmp = elementAt(loc1);
setElementAt(elementAt(loc2), loc1);
setElementAt(tmp, loc2);
}
} <font color="#009900">///:~ </PRE></font></font><DIV ALIGN=LEFT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">You
can now see the reason for the term “callback,” since the
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>quickSort( )</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
method “calls back” to the methods in
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Compare</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">.
You can also see how this technique has produced generic, reusable code.
</FONT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">To
use the
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>SortVector</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">,
you must create a class that implements
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Compare</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
for the kind of objects that you’re sorting. This is a place where an
inner class is not essential, but it can make sense for code organization.
Here’s an example for
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>String</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
objects:
</FONT><P></DIV>
<font color="#990000"><PRE><font color="#009900">//: StringSortTest.java</font>
<font color="#009900">// Testing the generic sorting Vector</font>
<font color="#0000ff">package</font> c08;
<font color="#0000ff">import</font> java.util.*;
<font color="#0000ff">public</font> <font color="#0000ff">class</font> StringSortTest {
<font color="#0000ff">static</font> <font color="#0000ff">class</font> StringCompare <font color="#0000ff">implements</font> Compare {
<font color="#0000ff">public</font> <font color="#0000ff">boolean</font> lessThan(Object l, Object r) {
<font color="#0000ff">return</font> ((String)l).toLowerCase().compareTo(
((String)r).toLowerCase()) < 0;
}
<font color="#0000ff">public</font> <font color="#0000ff">boolean</font>
lessThanOrEqual(Object l, Object r) {
<font color="#0000ff">return</font> ((String)l).toLowerCase().compareTo(
((String)r).toLowerCase()) <= 0;
}
}
<font color="#0000ff">public</font> <font color="#0000ff">static</font> <font color="#0000ff">void</font> main(String[] args) {
SortVector sv =
<font color="#0000ff">new</font> SortVector(<font color="#0000ff">new</font> StringCompare());
sv.addElement("d");
sv.addElement("A");
sv.addElement("C");
sv.addElement("c");
sv.addElement("b");
sv.addElement("B");
sv.addElement("D");
sv.addElement("a");
sv.sort();
Enumeration e = sv.elements();
<font color="#0000ff">while</font>(e.hasMoreElements())
System.out.println(e.nextElement());
}
} <font color="#009900">///:~ </PRE></font></font><DIV ALIGN=LEFT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">The
inner class is
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>static</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
because it does not need a link to an outer class in order for it to function.
</FONT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">You
can see how, once the framework is set up, it’s easy to reuse a design
like this – you simply write the class that encapsulates “the
things that change” and hand an object to the
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>SortVector</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">.</FONT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">The
comparison forces the strings to lower case, so that the capital
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>A</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">’s
end up next to the small
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>a</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">’s
and not in some entirely different place. This example shows, however, a slight
deficiency in this approach, since the test code above puts the uppercase and
lowercase single letters of the same letter in the order that they appear: A a
b B c C d D. This is not usually much of a problem, because you’re
usually working with longer strings and in that situation the effect
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -