Java 堆排序的应用--对类根据目标成员进行排序

Java 堆排序的应用--对类根据目标成员进行排序

Java 堆排序的应用--对类根据目标成员进行排序

• 前言
• 堆排序方案
• • 应用
• 快排方案
• 应用
• 代码记录
• 结语

前言

突然想对SQL语句搜索上来的数据重新排个序，也就是对类list排序。一时间网上搜了搜都说要覆写compareTo函数，觉得这么搞太烦了，想自己整一个排序又想简单一点。
于是突然想起堆排序了。堆排序的性能和快排的平均性能类似，所以计划用堆实现对类排序，顺带复习一下堆。

堆排序方案

• 用最小堆，并规定比较规则为对比期望对比字段的大小(->右侧的值决定参数1和参数2的大小关系)

//小堆
Queue heap =new PriorityQueue((n1, n2) -> n1.compareDeviceId(n2.getDeviceId()));

• 在类中规定一个比较方法

class UserDevice {
	private Integer deviceId;
	private String  userName;
	public UserDevice (String  userName,int deviceId){
		this.userName=userName;
		this.deviceId=deviceId;
	}
	public Integer getDeviceId() {
		return deviceId;
	}
	public void setDeviceId(Integer deviceId) {
		this.deviceId = deviceId;
	}
	public String getUserName() {
		return userName;
	}
	public void setUserName(String userName) {
		this.userName = userName;
	}
	
	//定义null最小
	public int compareDeviceId(Integer anotherInteger) {
		if(anotherInteger==null&&deviceId==null) 
			return 0;
		if(deviceId==null)
			return -1;
		if(anotherInteger==null)
			return 1;
		return deviceId.compareTo(anotherInteger);	
	}
}

应用

		//小堆
        Queue heap =new PriorityQueue((n1, n2) -> n1.compareDeviceId(n2.getDeviceId()));
    	for(UserDevice ud :userDevices) {
    		heap.offer(ud);
    	}
    	while(heap.size()>0) {
    		UserDevice ud = heap.poll(); 
    		System.out.println(ud.getUserName()+"----ID:"+ud.getDeviceId());
    	}

快排方案

堆排序完毕后，觉得还有精力就再琢磨一下快排的方案
一种方法是类实现Comparable接口，然后调用Collections.sort(List)方法进行排序，另一种方法是类不实现Comparable接口，而在排序时使用Collections.sort(List, Comparator)方法，并实现其中的Comparator接口。我采取的方法为后一种，因为需要排序的地方很少，但是用类的地方很多。

• 对类添加比较函数（或者分离到外部来）

public int compareTo(UserDevice ud) {
		if((ud==null||ud.getDeviceId()==null)&&deviceId==null) 
			return 0;
		if(deviceId==null)
			return -1;
		if(ud==null||ud.getDeviceId()==null)
			return 1;
		return deviceId.compareTo(ud.getDeviceId());
	}

应用

• 使用Collections.sort(List, Comparator)方法

		Collections.sort(userDevices,new Comparator() {
    		@Override
    		public int compare(UserDevice o1,UserDevice o2) {
    			if(o1==null&&(o2==null||o2.getDeviceId()==0))return 0;
    			if(o1==null)return -1;
    			return o1.compareTo(o2);
    		}
    	});
 
    	for(UserDevice ud :userDevices) {
    		System.out.println(ud.getUserName()+"----ID:"+ud.getDeviceId());
    	}

代码记录

public class testLearn {
	
	public static int  n = 1;
	
    public static void main(String[] args) {    	
    	try {
    		test();
		} catch (IOException e) {
			e.printStackTrace();
		} catch (Exception e) {
			// TODO 自动生成的 catch 块
			e.printStackTrace();
		}
    }
    
    
    
    public static void test() throws Exception {
    	ArrayList  userDevices= new  ArrayList();
    	userDevices.add(new UserDevice("张三",3));
    	userDevices.add(new UserDevice("李四",2));
    	userDevices.add(new UserDevice("王五",1));
    	
    	for(UserDevice ud :userDevices) {
    		System.out.println(ud.getUserName()+"----ID:"+ud.getDeviceId());
    	}
    	
    	//小堆
        Queue heap =new PriorityQueue((n1, n2) -> n1.compareDeviceId(n2.getDeviceId()));
    	for(UserDevice ud :userDevices) {
    		heap.offer(ud);
    	}
    	while(heap.size()>0) {
    		UserDevice ud = heap.poll(); 
    		System.out.println(ud.getUserName()+"----ID:"+ud.getDeviceId());
    	}
    	Collections.sort(userDevices,new Comparator() {
    		@Override
    		public int compare(UserDevice o1,UserDevice o2) {
    			if(o1==null&&(o2==null||o2.getDeviceId()==0))return 0;
    			if(o1==null)return -1;
    			return o1.compareTo(o2);
    		}
    	});
 
    	for(UserDevice ud :userDevices) {
    		System.out.println(ud.getUserName()+"----ID:"+ud.getDeviceId());
    	}
    	
    }
    
}
class UserDevice {
	private Integer deviceId;
	private String  userName;
	public UserDevice (String  userName,int deviceId){
		this.userName=userName;
		this.deviceId=deviceId;
	}
	public Integer getDeviceId() {
		return deviceId;
	}
	public void setDeviceId(Integer deviceId) {
		this.deviceId = deviceId;
	}
	public String getUserName() {
		return userName;
	}
	public void setUserName(String userName) {
		this.userName = userName;
	}
	
	//定义null最小
	public int compareDeviceId(Integer anotherInteger) {
		if(anotherInteger==null&&deviceId==null) 
			return 0;
		if(deviceId==null)
			return -1;
		if(anotherInteger==null)
			return 1;
		return deviceId.compareTo(anotherInteger);
		
	}
	public int compareTo(UserDevice ud) {
		if((ud==null||ud.getDeviceId()==null)&&deviceId==null) 
			return 0;
		if(deviceId==null)
			return -1;
		if(ud==null||ud.getDeviceId()==null)
			return 1;
		return deviceId.compareTo(ud.getDeviceId());
	}
}

结语

我最终思考了一下，还是用快排序性能好一些，或者直接将排序任务交给SQL。