分数排序的特殊问题
在java中实现排序远比C/C++简单,我们只要让集合中元素对应的类实现Comparable接口,然后调用Collections.sort();方法即可.
这种方法对于排序存在许多相同元素的情况有些浪费,明显即使值相等,两个元素之间也要比较一下,这在现实中是没有意义的.
典型例子就是学生成绩统计的问题,例如高考中,满分是150,成千上万的学生成绩都在0-150之间,平均一个分数的人数成百上千,这时如果排序还用传统方法明显就浪费了.
进一步思考
成绩既然有固定的分数等级,我们可以把相同等级的成绩放在一起,以100分为满分计,共分一百个等级,来一个成绩就归入固定的档,要得到排序结果时可以从低档取到高档,取出来自然就是排序的结果.
接下来是确定数据结构的问题,档次-学生群这样的自然是key-value结构,但Map中的Hashtable和HashMap都不能保持插入时的顺序,虽然我们可以从固定的档次取名单,但这样略嫌不方便,我们需要更好的数据结构,它既以键值的形式存储数据,又能保持插入时的顺序.
LinkedHashMap横空出世
LinkedHashMap正是这样一个数据结构,它”在HashMap的基础上增加了一个双向链表,由此LinkedHashMap既能以哈希表的形式存储数据,又能保持查询时的顺序.”
下页就是进行排序用的类,它在构造实例时先创建好分数档次,加入学生成绩时自动归档,要取出排序的学生的成绩时只要按档次输出即可.
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 "学生姓名="+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
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
