在分析许多开源Java项目的源代码时,我发现大多数开发人员仅以两种不同的方式实现排序。其中一种是基于使用类
sort()
方法Collections
或Arrays
,另一种是基于使用自排序数据结构,例如TreeMap
和TreeSet
。
使用 sort() 方法
如果您需要对集合进行排序,请使用Collections.sort()
.
// Collections.sort(…)
List<ObjectName> list = new ArrayList<ObjectName>();
Collections.sort(list, new Comparator<ObjectName>() {
public int compare(ObjectName o1, ObjectName o2) {
return o1.toString().compareTo(o2.toString());
}
});
如果需要对数组进行排序,请使用Arrays.sort()
.
// Arrays.sort(…)
ObjectName[] arr = new ObjectName[10];
Arrays.sort(arr, new Comparator<ObjectName>() {
public int compare(ObjectName o1, ObjectName o2) {
return o1.toString().compareTo(o2.toString());
}
});
sort()
当集合或数组已经充满值时, 该方法非常方便。
使用自排序数据结构
如果需要对列表 (List
) 或集合 ( Set
) 进行排序,请使用TreeSet
排序结构。
// TreeSet
Set<ObjectName> sortedSet = new TreeSet<ObjectName>(new Comparator<ObjectName>() {
public int compare(ObjectName o1, ObjectName o2) {
return o1.toString().compareTo(o2.toString());
}
});
sortedSet.addAll(unsortedSet);
如果需要对字典进行排序 ( Map
),请使用TreeMap
排序结构。TreeMap
按键 ( key
) 排序。
// TreeMap – использующий String ключи и компаратор (Comparator) CASE_INSENSITIVE_ORDER,
// упорядочивающий строки (String) методом compareToIgnoreCase
Map<String, Integer> sortedMap = new TreeMap<String, Integer>(String.CASE_INSENSITIVE_ORDER);
sortedMap.putAll(unsortedMap);
//TreeMap – общий случай, компаратор указывается вручную
Map<ObjectName, String> sortedMap = new TreeMap<ObjectName, String>(new Comparator<ObjectName>() {
public int compare(ObjectName o1, ObjectName o2) {
return o1.toString().compareTo(o2.toString());
}
});
sortedMap.putAll(unsortedMap);
当您需要对集合中的元素执行大量搜索时,上述方法非常有用。自排序数据结构的效率O(log(n))
优于O(n)
. 这意味着当集合中的数据量增加一倍时,搜索时间不会增加一倍,而是以恒定量 增加。
排序问题的错误方法
您仍然可以找到程序员独立描述排序算法的示例。考虑下面给出的排序代码(按升序对双精度数组进行排序)。这段代码不仅效率低下,而且不可读。这样的例子还有很多。double t;
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++)
if (r[j] < r[i]) {
t = r[i];
r[i] = r[j];
r[j] = t;
}
GO TO FULL VERSION