分數排序的特殊問題
在java中實現排序遠比C/C++簡單,我們只要讓集合中元素對應的類實現Comparable接口,然后調用Collections.sort();方法即可.
這種方法對于排序存在許多相同元素的情況有些浪費,明顯即使值相等,兩個元素之間也要比較一下,這在現實中是沒有意義的.
典型例子就是學生成績統計的問題,例如高考中,滿分是150,成千上萬的學生成績都在0-150之間,平均一個分數的人數成百上千,這時如果排序還用傳統方法明顯就浪費了.
進一步思考
成績既然有固定的分數等級,我們可以把相同等級的成績放在一起,以100分為滿分計,共分一百個等級,來一個成績就歸入固定的檔,要得到排序結果時可以從低檔取到高檔,取出來自然就是排序的結果.
接下來是確定數據結構的問題,檔次-學生群這樣的自然是key-value結構,但Map中的Hashtable和HashMap都不能保持插入時的順序,雖然我們可以從固定的檔次取名單,但這樣略嫌不方便,我們需要更好的數據結構,它既以鍵值的形式存儲數據,又能保持插入時的順序.
LinkedHashMap橫空出世
LinkedHashMap正是這樣一個數據結構,它”在HashMap的基礎上增加了一個雙向鏈表,由此LinkedHashMap既能以哈希表的形式存儲數據,又能保持查詢時的順序.”
下頁就是進行排序用的類,它在構造實例時先創建好分數檔次,加入學生成績時自動歸檔,要取出排序的學生的成績時只要按檔次輸出即可.
ScoreSorter類
輔助類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 "學生姓名="+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<100000;i++){
scores.add(new Student("學生"+i,random.nextInt(100)));
}
Collections.sort(scores);
//for(Student student:scores){
// System.out.println(student);
//}
oldSortTest.end("老排序方案耗時");*/
//-----------新排序方案-----------
TimeTest newSortTest=new TimeTest();
ScoreSorter sorter2=new ScoreSorter(100);
Random random=new Random();
for(int i=0;i<1000;i++){
sorter2.addStudent(new Student("學生"+i,random.nextInt(100)));
}
List<Student> ls=sorter2.getSortedScores();
//for(Student student:sorter2.getSortedScores()){
// System.out.println(student);
//}
newSortTest.end("新排序方案耗時");
}
}
與傳統排序方案的比較
在元素個數遠超等級個數即相同的元素很多時,這種方案在速度上稍高于傳統方案,節省的時間主要在不比較同等級元素上.
這種方案能夠按檔次取出數據,這種優勢是傳統排序方案缺乏的.
傳統方案普適性比此方案強.
源碼：scoresorter
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
