考試分數排序是一種特殊的排序方式，從0分到最高分都可能有成績存在，如果考生數量巨大如高考，大量考生都在同一分數上，如果需要從低到高排序的話，很多同樣分數的成績也被比較了，這對排序結果是沒有意義的，因為同一分數不需要比較，對于這種情況如果使用傳統排序就會有浪費，如果先按分數建立好檔次，再把考生成績按分數放入檔次就可以了。下面分別列出了三種方案的代碼和比較結果：
學生類：
package com.junglesong;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
public class Student implements Comparable
{
private String name;
private int score;
public Student(String name,int score){
this.name=name;
this.score=score;
}
public int compareTo(Object obj){
Student another=(Student)obj;
return this.score-another.score;
}
public String toString(){
return "學生姓名="+name+" 分數="+score;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getScore() {
return score;
}
public void setScore(int score) {
this.score = score;
}
}
第一種傳統排序方案的代碼：
public static void main(String[] args){
//-----------老排序方案-----------
TimeTest oldSortTest=new TimeTest();
List<Student> scores=new ArrayList<Student>();
Random random=new Random();
for(int i=0;i<1000*100;i++){
scores.add(new Student("學生"+i,random.nextInt(100)));
}
Collections.sort(scores);
/**//*for(Student student:scores){
System.out.println(student);
}*/
oldSortTest.end("老排序方案耗時");
}
第二種使用LinkedLinkedHashMap分檔排序：
package com.junglesong;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
/** *//**
* 學生分數排序類(LinkedHashMap實現)
* @author: sitinspring(junglesong@gmail.com)
* @date: 2008-3-4
*/
public class LinkedHashMapScoreSorter{
/** *//**
* 學生成績單
*/
private Map<Integer,List<Student>> scoreSheet;
/** *//**
* 滿分分數
*/
private final int maxScore;
/** *//**
* 構造函數
* @param MaxScore: 滿分分數
*/
public LinkedHashMapScoreSorter(int MaxScore){
this.maxScore=MaxScore;
scoreSheet=new LinkedHashMap<Integer,List<Student>>();
for(int i=0;i<=maxScore;i++){
List<Student> ls=new ArrayList<Student>();
scoreSheet.put(i, ls);
}
}
/** *//**
* 添加一個學生成績
* @param student
*/
public void addStudent(Student student){
int score=student.getScore();
if(student.getScore()>maxScore){
return;
}
List<Student> ls=scoreSheet.get(score);
ls.add(student);
}
/** *//**
* 得到從低到高的學生成績表
*
*/
@SuppressWarnings("unchecked")
public List<Student> getSortedScores(){
List<Student> retval=new ArrayList<Student>();
Iterator it=scoreSheet.values().iterator();
while(it.hasNext()){
List<Student> ls=(List<Student>)it.next();
retval.addAll(ls);
}
return retval;
}
public static void main(String[] args){
TimeTest sortTest=new TimeTest();
int maxScore=100;
LinkedHashMapScoreSorter sorter2=new LinkedHashMapScoreSorter(maxScore);
Random random=new Random();
for(int i=0;i<1000*100;i++){
sorter2.addStudent(new Student("學生"+i,random.nextInt(maxScore+1)));
}
sortTest.end("LinkedHashMap排序方案耗時");
List<Student> ls=sorter2.getSortedScores();
/**//*for(Student student:ls){
System.out.println(student);
}*/
}
}
第三種使用數組實現分檔：
package com.junglesong;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import org.apache.log4j.Logger;
/** *//**
* 學生分數排序類(數組實現)
* @author: sitinspring(junglesong@gmail.com)
* @date: 2008-3-4
*/
public class ArrayScoreSorter{
/** *//**
* 學生成績單
*/
private List<Student>[] scoreSheet;
/** *//**
* 滿分分數
*/
private final int maxScore;
/** *//**
* 構造函數
* @param MaxScore: 滿分分數
*/
@SuppressWarnings("unchecked")
public ArrayScoreSorter(int MaxScore){
this.maxScore=MaxScore;
scoreSheet=new ArrayList[this.maxScore+1];
for(int i=0;i<=maxScore;i++){
scoreSheet[i]=new ArrayList<Student>();
}
}
/** *//**
* 添加一個學生成績
* @param student
*/
public void addStudent(Student student){
int score=student.getScore();
if(student.getScore()>maxScore){
return;
}
List<Student> ls=scoreSheet[score];
ls.add(student);
}
/** *//**
* 得到從低到高的學生成績表
*
*/
@SuppressWarnings("unchecked")
public List<Student> getSortedScores(){
List<Student> retval=new ArrayList<Student>();
for(List<Student> ls:scoreSheet){
retval.addAll(ls);
}
return retval;
}
public static void main(String[] args){
TimeTest sortTest=new TimeTest();
int maxScore=100;
ArrayScoreSorter sorter=new ArrayScoreSorter(maxScore);
Random random=new Random();
for(int i=0;i<1000*100;i++){
sorter.addStudent(new Student("學生"+i,random.nextInt(maxScore+1)));
}
sortTest.end("數組排序方案耗時");
List<Student> ls=sorter.getSortedScores();
/**//*for(Student student:ls){
System.out.println(student);
}*/
}
}
比較結果如下：
2008-03-10 20:53:52,218 INFO [main] (TimeTest.java:28) - LinkedHashMap排序方案耗時 453毫秒
2008-03-10 20:53:56,140 INFO [main] (TimeTest.java:28) - LinkedHashMap排序方案耗時 438毫秒
2008-03-10 20:53:59,031 INFO [main] (TimeTest.java:28) - LinkedHashMap排序方案耗時 453毫秒
2008-03-10 20:54:02,000 INFO [main] (TimeTest.java:28) - LinkedHashMap排序方案耗時 485毫秒
2008-03-10 20:54:04,453 INFO [main] (TimeTest.java:28) - LinkedHashMap排序方案耗時 453毫秒
2008-03-10 20:54:07,421 INFO [main] (TimeTest.java:28) - LinkedHashMap排序方案耗時 437毫秒
2008-03-10 20:54:10,531 INFO [main] (TimeTest.java:28) - LinkedHashMap排序方案耗時 437毫秒
2008-03-10 20:54:13,359 INFO [main] (TimeTest.java:28) - LinkedHashMap排序方案耗時 453毫秒
2008-03-10 20:54:20,250 INFO [main] (TimeTest.java:28) - 老排序方案耗時 500毫秒
2008-03-10 20:54:23,421 INFO [main] (TimeTest.java:28) - 老排序方案耗時 485毫秒
2008-03-10 20:54:26,812 INFO [main] (TimeTest.java:28) - 老排序方案耗時 500毫秒
2008-03-10 20:54:30,093 INFO [main] (TimeTest.java:28) - 老排序方案耗時 515毫秒
2008-03-10 20:54:32,968 INFO [main] (TimeTest.java:28) - 老排序方案耗時 500毫秒
2008-03-10 20:54:35,906 INFO [main] (TimeTest.java:28) - 老排序方案耗時 516毫秒
2008-03-10 20:54:38,953 INFO [main] (TimeTest.java:28) - 老排序方案耗時 516毫秒
2008-03-10 20:54:41,796 INFO [main] (TimeTest.java:28) - 老排序方案耗時 515毫秒
2008-03-10 20:54:45,671 INFO [main] (TimeTest.java:28) - 老排序方案耗時 500毫秒
2008-03-10 20:54:48,921 INFO [main] (TimeTest.java:28) - 老排序方案耗時 500毫秒
2008-03-10 20:54:56,500 INFO [main] (TimeTest.java:28) - 數組排序方案耗時 422毫秒
2008-03-10 20:54:59,250 INFO [main] (TimeTest.java:28) - 數組排序方案耗時 422毫秒
2008-03-10 20:55:01,921 INFO [main] (TimeTest.java:28) - 數組排序方案耗時 437毫秒
2008-03-10 20:55:05,281 INFO [main] (TimeTest.java:28) - 數組排序方案耗時 438毫秒
2008-03-10 20:55:08,484 INFO [main] (TimeTest.java:28) - 數組排序方案耗時 438毫秒
2008-03-10 20:55:11,250 INFO [main] (TimeTest.java:28) - 數組排序方案耗時 422毫秒
2008-03-10 20:55:14,234 INFO [main] (TimeTest.java:28) - 數組排序方案耗時 422毫秒
2008-03-10 20:55:17,312 INFO [main] (TimeTest.java:28) - 數組排序方案耗時 422毫秒
2008-03-10 20:55:20,546 INFO [main] (TimeTest.java:28) - 數組排序方案耗時 437毫秒
2008-03-10 20:55:24,500 INFO [main] (TimeTest.java:28) - 數組排序方案耗時 422毫秒
2008-03-10 20:55:27,640 INFO [main] (TimeTest.java:28) - 數組排序方案耗時 437毫秒
2008-03-10 20:55:30,750 INFO [main] (TimeTest.java:28) - 數組排序方案耗時 422毫秒
2008-03-10 20:55:34,171 INFO [main] (TimeTest.java:28) - 數組排序方案耗時 421毫秒
結果不難預料，數組方案平均最低，LinkedHashMap次之，因為它還要花時間產生hashCode,傳統排序最低，因為對相同數據進行比較無謂的浪費了時間。
程序下載：
http://www.tkk7.com/Files/junglesong/ScoreSorter20080310212653.rar