使用Java中Comparator接口实现自定义排序

一般情况下,自己动手写一个简单排序程序还是没有问题的,但是你能保证写出来的排序程序的时间复杂度吗?你能保证程序的正确性吗,鲁棒性呢,还有程序结构的清晰性,可维护性.......综上所述,学习一下排序接口来实现对复杂对象的排序还是很有必要的。Java中有两个用来实现排序的接口Comparator和Comparable接口,本人比较喜欢使用java的Comparator接口,在程序里实现Comparator接口里的compare(Object o1,Object o2)方法,然后在程序中通过调用Arrays.sort(array,new DemoClass())或者Collections.sort(collection,new DemoClass())来实现对对象数组的排序,直接上一栗子:

描述:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

思路:

本来想模仿合并两个链表的方法,查找所有的lists链表一遍找出一个最小值,并将最小值链接到结果链表中,并将最小结点删除,将最小结点的next结点替代之,直至为null,将链表删去。
但是当lists.size()比较大时,时间复杂度就上来了,而且每次只能选一个最小结点,O(N*N)的节奏。。。
所以,想到不就是排序么,将所有的结点集合到一起,然后对其进行快速排序不就可以了么,啊哈,真的是这样,bravo!
很显然,这种方法肯定不是最优方法,但是时间复杂度也只是O(N*logN),也是可以接受的。

代码:

public class Solution implements Comparator<ListNode> {
	public int compare(ListNode t1, ListNode t2) {
		return t1.val - t2.val;
	}

	public ListNode mergeKLists(List<ListNode> lists) {
		if (lists == null || lists.size() == 0)
			return null;
		if (lists.size() == 1)// just have one linkedlist
			return lists.get(0);
		int i=0,len=0;
		List<ListNode> returnList = new ArrayList<ListNode>();
		ListNode cur = null;
		for (i = 0; i < lists.size(); i++) {
			cur = lists.get(i);
			while (cur != null) {
				returnList.add(cur);
				cur = cur.next;
			}
		}
		Collections.sort(returnList, new Solution());
		ListNode pre = returnList.get(0);
		cur = null;
		len = returnList.size();
		for (i = 1; i < len; i++) {
			cur = returnList.get(i);
			pre.next = cur;
			pre = cur;
		}
		returnList.get(len - 1).next = null;
		return returnList.get(0);
	}
}



郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。