考试分数排序是一种特殊的排序方式，从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.blogjava.net/Files/junglesong/ScoreSorter20080310212653.rar