分?jǐn)?shù)排序的特殊問題
在java中實現(xiàn)排序遠(yuǎn)比C/C++簡單,我們只要讓集合中元素對應(yīng)的類實現(xiàn)Comparable接口,然后調(diào)用Collections.sort();方法即可.
這種方法對于排序存在許多相同元素的情況有些浪費,明顯即使值相等,兩個元素之間也要比較一下,這在現(xiàn)實中是沒有意義的.
典型例子就是學(xué)生成績統(tǒng)計的問題,例如高考中,滿分是150,成千上萬的學(xué)生成績都在0-150之間,平均一個分?jǐn)?shù)的人數(shù)成百上千,這時如果排序還用傳統(tǒng)方法明顯就浪費了.
進(jìn)一步思考
成績既然有固定的分?jǐn)?shù)等級,我們可以把相同等級的成績放在一起,以100分為滿分計,共分一百個等級,來一個成績就歸入固定的檔,要得到排序結(jié)果時可以從低檔取到高檔,取出來自然就是排序的結(jié)果.
接下來是確定數(shù)據(jù)結(jié)構(gòu)的問題,檔次-學(xué)生群這樣的自然是key-value結(jié)構(gòu),但Map中的Hashtable和HashMap都不能保持插入時的順序,雖然我們可以從固定的檔次取名單,但這樣略嫌不方便,我們需要更好的數(shù)據(jù)結(jié)構(gòu),它既以鍵值的形式存儲數(shù)據(jù),又能保持插入時的順序.
LinkedHashMap橫空出世
LinkedHashMap正是這樣一個數(shù)據(jù)結(jié)構(gòu),它”在HashMap的基礎(chǔ)上增加了一個雙向鏈表,由此LinkedHashMap既能以哈希表的形式存儲數(shù)據(jù),又能保持查詢時的順序.”
下頁就是進(jìn)行排序用的類,它在構(gòu)造實例時先創(chuàng)建好分?jǐn)?shù)檔次,加入學(xué)生成績時自動歸檔,要取出排序的學(xué)生的成績時只要按檔次輸出即可.
ScoreSorter類
輔助類Student
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
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("老排序方案耗時");*/ //-----------新排序方案----------- 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("新排序方案耗時"); }} |
與傳統(tǒng)排序方案的比較
在元素個數(shù)遠(yuǎn)超等級個數(shù)即相同的元素很多時,這種方案在速度上稍高于傳統(tǒng)方案,節(jié)省的時間主要在不比較同等級元素上.
這種方案能夠按檔次取出數(shù)據(jù),這種優(yōu)勢是傳統(tǒng)排序方案缺乏的.
傳統(tǒng)方案普適性比此方案強(qiáng).
源碼：scoresorter
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
