分?jǐn)?shù)排序的特殊問(wèn)題
在java中實(shí)現(xiàn)排序遠(yuǎn)比C/C++簡(jiǎn)單,我們只要讓集合中元素對(duì)應(yīng)的類(lèi)實(shí)現(xiàn)Comparable接口,然后調(diào)用Collections.sort();方法即可.
這種方法對(duì)于排序存在許多相同元素的情況有些浪費(fèi),明顯即使值相等,兩個(gè)元素之間也要比較一下,這在現(xiàn)實(shí)中是沒(méi)有意義的.
典型例子就是學(xué)生成績(jī)統(tǒng)計(jì)的問(wèn)題,例如高考中,滿分是150,成千上萬(wàn)的學(xué)生成績(jī)都在0-150之間,平均一個(gè)分?jǐn)?shù)的人數(shù)成百上千,這時(shí)如果排序還用傳統(tǒng)方法明顯就浪費(fèi)了.
進(jìn)一步思考
成績(jī)既然有固定的分?jǐn)?shù)等級(jí),我們可以把相同等級(jí)的成績(jī)放在一起,以100分為滿分計(jì),共分一百個(gè)等級(jí),來(lái)一個(gè)成績(jī)就歸入固定的檔,要得到排序結(jié)果時(shí)可以從低檔取到高檔,取出來(lái)自然就是排序的結(jié)果.
接下來(lái)是確定數(shù)據(jù)結(jié)構(gòu)的問(wèn)題,檔次-學(xué)生群這樣的自然是key-value結(jié)構(gòu),但Map中的Hashtable和HashMap都不能保持插入時(shí)的順序,雖然我們可以從固定的檔次取名單,但這樣略嫌不方便,我們需要更好的數(shù)據(jù)結(jié)構(gòu),它既以鍵值的形式存儲(chǔ)數(shù)據(jù),又能保持插入時(shí)的順序.
LinkedHashMap橫空出世
LinkedHashMap正是這樣一個(gè)數(shù)據(jù)結(jié)構(gòu),它”在HashMap的基礎(chǔ)上增加了一個(gè)雙向鏈表,由此LinkedHashMap既能以哈希表的形式存儲(chǔ)數(shù)據(jù),又能保持查詢時(shí)的順序.”
下頁(yè)就是進(jìn)行排序用的類(lèi),它在構(gòu)造實(shí)例時(shí)先創(chuàng)建好分?jǐn)?shù)檔次,加入學(xué)生成績(jī)時(shí)自動(dòng)歸檔,要取出排序的學(xué)生的成績(jī)時(shí)只要按檔次輸出即可.
ScoreSorter類(lèi)
package com.junglesong;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
/** *//**
* 學(xué)生分?jǐn)?shù)排序類(lèi)
* @author: sitinspring(junglesong@gmail.com)
* @date: 2008-3-4
*/
public class ScoreSorter
{
/** *//**
* 學(xué)生成績(jī)單
*/
private Map<Integer,List<Student>> scoreSheet;
/** *//**
* 滿分分?jǐn)?shù)
*/
private final int maxScore;
/** *//**
* 構(gòu)造函數(shù)
* @param MaxScore: 滿分分?jǐn)?shù)
*/
public ScoreSorter(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);
}
}
/** *//**
* 添加一個(gè)學(xué)生成績(jī)
* @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);
}
/** *//**
* 得到從低到高的學(xué)生成績(jī)表
*
*/
@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;
}
}
輔助類(lèi)Student
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 "學(xué)生姓名="+name+" 分?jǐn)?shù)="+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<100000;i++){
scores.add(new Student("學(xué)生"+i,random.nextInt(100)));
}
Collections.sort(scores);
//for(Student student:scores){
// System.out.println(student);
//}
oldSortTest.end("老排序方案耗時(shí)");*/
//-----------新排序方案-----------
TimeTest newSortTest=new TimeTest();
ScoreSorter sorter2=new ScoreSorter(100);
Random random=new Random();
for(int i=0;i<1000;i++){
sorter2.addStudent(new Student("學(xué)生"+i,random.nextInt(100)));
}
List<Student> ls=sorter2.getSortedScores();
//for(Student student:sorter2.getSortedScores()){
// System.out.println(student);
//}
newSortTest.end("新排序方案耗時(shí)");
}
}
與傳統(tǒng)排序方案的比較
在元素個(gè)數(shù)遠(yuǎn)超等級(jí)個(gè)數(shù)即相同的元素很多時(shí),這種方案在速度上稍高于傳統(tǒng)方案,節(jié)省的時(shí)間主要在不比較同等級(jí)元素上.
這種方案能夠按檔次取出數(shù)據(jù),這種優(yōu)勢(shì)是傳統(tǒng)排序方案缺乏的.
傳統(tǒng)方案普適性比此方案強(qiáng).
http://www.aygfsteel.com/Files/junglesong/ScoreSorter20080304222012.rar