Java集合框架针对不同的数据结构提供了多种排序的方法,
虽然很多时候我们可以自己实现排序,比如数组等,但是灵活的使用JDK提供的排序方法,可以提高开发效率,而且通常JDK的实现要比自己造的轮子性能更优化。
1.使用Arrays对数组进行排序
Java API对Arrays类的说明是:此类包含用来操作数组(比如排序和搜索)的各种方法。
(1)使用Arrays排序
Arrays使用非常简单,直接调用sort()即可:
1
2
3
4
5
6
7
8
9
10
11
|
int
[] arr =
new
int
[] {
5
,
8
,-
2
,
0
,
10
};
Arrays.sort(arr);
for
(
int
i=
0
;i<arr.length;i++){
System.out.print(arr[i]+
","
);
}
char
[] charArr =
new
char
[] {
'b'
,
'a'
,
'c'
,
'd'
,
'D'
};
Arrays.sort(charArr);
for
(
int
i=
0
;i<arr.length;i++){
System.out.print(charArr[i]+
","
);
}
|
如果需要降序排序, 升序排序后逆序即可:
1
|
Collections.reverse(Arrays.asList(arr));
|
(2)Arrays.sort()的实现
查看源码会发现,Arrays.sort()有许多重载的方法,如sort(int[] a)、sort(long[] a) 、sort(char[] a)等,
1
2
3
|
public
static
void
sort(
int
[] a) {
DualPivotQuicksort.sort(a);
}
|
但最终都是调用了DualPivotQuicksort.sort(a)的方法,
这是一个改进的快速排序,采用多路快速排序法,比单路快速排序法有更好的性能,
并且根据数组长度不同会最终选择不同的排序实现,
看一下这个方法的实现,这里不作展开:
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
|
public
static
void
sort(
char
[] a) {
sort(a,
0
, a.length -
1
);
}
public
static
void
sort(
char
[] a,
int
left,
int
right) {
// Use counting sort on large arrays
if
(right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
int
[] count =
new
int
[NUM_CHAR_VALUES];
for
(
int
i = left -
1
; ++i <= right;
count[a[i]]++
);
for
(
int
i = NUM_CHAR_VALUES, k = right +
1
; k > left; ) {
while
(count[--i] ==
0
);
char
value = (
char
) i;
int
s = count[i];
do
{
a[--k] = value;
}
while
(--s >
0
);
}
}
else
{
// Use Dual-Pivot Quicksort on small arrays
doSort(a, left, right);
}
}
|
1
2
3
4
5
6
|
private
static
void
doSort(
char
[] a,
int
left,
int
right) {
// Use Quicksort on small arrays
if
(right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right,
true
);
return
;
}
|
2.使用Comparator或Comparable进行自定义排序
集合框架中,Collections工具类支持两种排序方法:
Collections.sort(List<T> list);
Collections.sort(List<T> list, Comparator<? super T> c)
如果待排序的列表中是数字或者字符,可以直接使用Collections.sort(list);
当需要排序的集合或数组不是单纯的数字型时,需要自己定义排序规则,实现一个Comparator比较器。
下面了解一下Comparable和Comparator的应用。
Comparable 是排序接口,一个类实现了Comparable接口,就意味着该类支持排序。
Comparable 的定义如下:
1
2
3
|
public
interface
Comparable<T> {
public
int
compareTo(T o);
}
|
接口中通过x.compareTo(y) 来比较x和y的大小。若返回负数,意味着x比y小;返回零,意味着x等于y;返回正数,意味着x大于y。
当然这里的大于等于小于的意义是要根据我们的排序规则来理解的。
Comparator是比较器接口,如果需要控制某个类的次序,而该类本身没有实现Comparable接口,也就是不支持排序,那么可以建立一个类需要实现Comparator接口即可,在这个接口里制定具体的排序规则,
Comparator接口的定义如下:
1
2
3
4
|
public
interface
Comparator<T> {
int
compare(T o1, T o2);
boolean
equals(Object obj);
}
|
一个比较器类要实现Comparator接口一定要实现compareTo(T o1, T o2) 函数,如果没有必要,可以不去重写equals() 函数。
因为在Object类中已经实现了equals(Object obj)函数方法。
int compare(T o1, T o2) 和上面的x.compareTo(y)类似,定义排序规则后返回正数,零和负数分别代表大于,等于和小于。
3.如何对HashMap的key或者value排序
HashMap作为kay-value结构,本身是无序的,排序比较灵活,一般会通过一个list进行保存。
下面的代码针对HashMap的key和value排序,提供几种实现的思路:
(1)转换为key数组,按照key排序
1
2
3
4
5
|
Object[] key_arr = hashmap.keySet().toArray();
Arrays.sort(key_arr);
for
(Object key : key_arr) {
Object value = hashmap.get(key);
}
|
(2)对HashMap的value进行排序
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
|
/**
* 针对HashMap的value进行排序
* @author Bingyue
*/
public
class
HashMapSort {
public
static
void
main(String[] args) {
HashMap<String, Integer> map =
new
HashMap<String, Integer>(){{
put(
"tom"
,
18
);
put(
"jack"
,
25
);
put(
"susan"
,
20
);
put(
"rose"
,
38
);
}};
ValueComparator cmptor =
new
ValueComparator(map);
/**
* 转换为有序的TreeMap进行输出
*/
TreeMap<String, Integer> sorted_map =
new
TreeMap<String, Integer>(cmptor);
sorted_map.putAll(map);
for
(String sortedkey : sorted_map.keySet()){
System.out.println(sortedkey+map.get(sortedkey));
}
/**
* 转换为有序的list进行排序
*/
List<String> keys =
new
ArrayList<String>(map.keySet());
Collections.sort(keys, cmptor);
for
(String key : keys) {
System.out.println(key+map.get(key));
}
}
static
class
ValueComparator
implements
Comparator<String> {
HashMap<String, Integer> base_map;
public
ValueComparator(HashMap<String, Integer> base_map) {
this
.base_map = base_map;
}
public
int
compare(String arg0, String arg1) {
if
(!base_map.containsKey(arg0) || !base_map.containsKey(arg1)) {
return
0
;
}
//按照value从小到大排序
if
(base_map.get(arg0) < base_map.get(arg1)) {
return
-
1
;
}
else
if
(base_map.get(arg0) == base_map.get(arg1)) {
return
0
;
}
else
{
return
1
;
}
}
}
}
|
输出:
tom18
susan20
jack25
rose38
tom18
susan20
jack25
rose38
4.通过Comparator自定义实体排序
如果你的List包装的是基本类型或者String,只要Collections.sort(list)即可,
但是如果list中保存的是实体bean等,就需要自己定义排序规则。
Java可以对ArrayList中的对象按照该对象某属性排序,下面的操作实现对Person实体列表的排序:
(1)定义Person实体类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public
class
Person{
String name;
int
age;
public
Person(String name,
int
age){
this
.name = name;
this
.age = age;
}
public
int
getAge() {
return
age;
}
public
void
setAge(
int
age) {
this
.age = age;
}
public
String getName() {
return
name;
}
public
void
setName(String name) {
this
.name = name;
}
}
|
(2)实现Comparator接口,编写排序规则
1
2
3
4
5
6
7
8
9
10
|
public
class
Mycomparator
implements
Comparator{<br>
// 实现Comparator接口,也就是定义排序规则
public
int
compare(Object o1,Object o2) {
Person p1=(Person)o1;
Person p2=(Person)o2;
if
(p1.age<p2.age)
return
1
;
else
return
0
;
}
}
|
(3)测试排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public
class
ListSort {
public
static
void
main(String[] args){
ArrayList list =
new
ArrayList();
list.add(
new
Person(
"lcl"
,
28
));
list.add(
new
Person(
"fx"
,
23
));
list.add(
new
Person(
"wqx"
,
29
));
Comparator comp =
new
Mycomparator();
Collections.sort(list,comp);
for
(
int
i =
0
;i<list.size();i++){
Person p = (Person)list.get(i);
System.out.println(p.getName());
}
}
}
|