コンパレータ

6588 ワード

一、Arrays類
「java.util.Arrays.sort()」は配列ソート操作ですが、実際にはjava.utilパッケージのArraysクラスのsort()メソッドを呼び出して完了します.Arraysは配列操作のツールクラスです(配列は一般的に使用されていないので、このツールクラスは意味がありません).
例:Arraysクラスの使用

import java.util.Arrays;

public class TestDemo {
	public static void main(String[] args) throws Exception {
		int dataA[] = new int[] { 1, 2, 3 };
		int dataB[] = new int[] { 1, 2, 3 };
		System.out.println(Arrays.equals(dataA, dataB));
		Arrays.fill(dataA, 9);
		System.out.println(Arrays.toString(dataA));
	}
}

配列の使用が減少するにつれて、このような操作も少なくなります.
次に、Arraysクラスに存在する1つの方法を観察する.

オブジェクト配列ソート:public static void sort(Object[]a);

例:ソートの実装

import java.util.Arrays;

class Person {
	private String name;
	private int age;

	public Person(String name, int age) {
		this.name = name;
		this.age = age;
	}

	public String toString() {
		return "  ：" + this.name + "，  ：" + this.age;
	}
}

public class TestDemo {
	public static void main(String[] args) throws Exception {
		Person per[] = new Person[] { new Person("  ", 20), new Person("  ", 18), new Person("  ", 25) };
		Arrays.sort(per); //   
		for (int x = 0; x < per.length; x++) {
			System.out.println(per[x]);
		}
	}
}
Exception in thread"main"java.lang.ClassCastException:
cn.mldn.demo.Person cannot
be cast
to java.lang.Comparable

PersonクラスにComparableインタフェースを実装する必要があることがわかりました.これがコンパレータです.
二、Comparableインタフェース
JAva.lang.Comparableインタフェースは最も一般的な比較器であり、このインタフェースは以下のように定義されています.

public interface Comparable {
	public int compareTo(T o);
}

ComparableインタフェースにはcomparareTo()メソッドが1つしかないことがわかり、このメソッドは-1(小)、0(等)、1(大)の3種類のデータを返すことができます.
前にString類を勉強した時もcompareTo()メソッドを勉強したことがありますが、当時のメソッドでは大きさの判断が可能でした.
例:コンパレータの使用

import java.util.Arrays;

class Person implements Comparable {
	private String name;
	private int age;

	public Person(String name, int age) {
		this.name = name;
		this.age = age;
	}

	public String toString() {
		return "  ：" + this.name + "，  ：" + this.age;
	}

	@Override
	public int compareTo(Person o) {
		if (this.age > o.age) {
			return 1;
		} else if (this.age < o.age) {
			return -1;
		}
		return 0;
	}
}

public class TestDemo {
	public static void main(String[] args) throws Exception {
		Person per[] = new Person[] { new Person("  ", 20), new Person("  ", 18), new Person("  ", 25) };
		Arrays.sort(per); //   
		for (int x = 0; x < per.length; x++) {
			System.out.println(per[x]);
		}
	}
}

以降は、オブジェクトのグループのサイズ比較であれば必ずComparableインタフェースを使用します.
三、二叉木実現:Binary Tree
オブジェクト間のサイズ比較操作が知られている以上、この概念を利用してツリー開発を実現することができ、ツリーの基本原則は以下の通りである.

1ノードの下には、左サブツリーと右サブツリーと呼ばれる2つのノードが保存されます.

最初のデータをルートノードとして取り、ルートノードより小さいデータは左サブツリーに、ルートノードより大きいデータは右サブツリーに置く.

出力時には、中順に(左-中-右)を巡回してデータの取り出しを行う.

例:次はComparableによるツリー操作

サイズ関係は、ComparableインタフェースのcomparareTo()メソッドによって実現される.

class Person implements Comparable {
	private String name;
	private int age;

	public Person(String name, int age) {
		this.name = name;
		this.age = age;
	}

	public String toString() {
		return "  ：" + this.name + "，  ：" + this.age;
	}

	@Override
	public int compareTo(Person o) {
		if (this.age > o.age) {
			return 1;
		} else if (this.age < o.age) {
			return -1;
		}
		return 0;
	}
}

@SuppressWarnings("rawtypes")
class BinaryTree {
	private class Node { //         
		private Comparable data; //       Comparable    
		private Node left; //    
		private Node right; //    

		public Node(Comparable data) {
			this.data = data;
		}

		@SuppressWarnings("unchecked")
		public void addNode(Node newNode) {
			if (this.data.compareTo(newNode.data) > 0) {
				if (this.left == null) {
					this.left = newNode;
				} else {
					this.left.addNode(newNode);
				}
			} else {
				if (this.right == null) {
					this.right = newNode;
				} else {
					this.right.addNode(newNode);
				}
			}
		}

		public void toArrayNode() {
			if (this.left != null) { //     
				this.left.toArrayNode();
			}
			BinaryTree.this.retData[BinaryTree.this.foot++] = this.data;
			if (this.right != null) {
				this.right.toArrayNode();
			}
		}
	}

	// ======================================
	private Node root; //    
	private int count; //          
	private int foot; //     
	private Object[] retData;

	public void add(Comparable data) {
		if (data == null) {
			return;
		}
		Node newNode = new Node(data); //            
		if (this.root == null) { //        
			this.root = newNode; //             
		} else { //           
			this.root.addNode(newNode);
		}
		this.count++; //       
	}

	public Object[] toArray() {
		if (this.root == null) {
			return null;
		}
		this.foot = 0;
		this.retData = new Object[this.count]; //          
		this.root.toArrayNode();
		return this.retData;
	}
}

public class BinaryTreeDemo {
	public static void main(String[] args) {
		BinaryTree bt = new BinaryTree();
		bt.add(new Person("  ", 20));
		bt.add(new Person("  ", 18));
		bt.add(new Person("  ", 25));
		Object[] data = bt.toArray();
		for (int x = 0; x < data.length; x++) {
			System.out.println(data[x]);
		}
	}
}

四、救済の比較器:Comparatorインタフェース
作業中にコンパレータを使用する場合は、Comparableが優先されますが、クラス定義時にインタフェースを実装する必要があるという特徴があります.しかし、クラスが開発済みで、これ以上変更は許されません.このような場合、オブジェクト配列のソートの問題は考慮されません.後期にまたこの問題を提起した.しかし、コードは変更できません.では、このときどのようにソートしますか?
例:開発されたクラス

class Person {
	private String name;
	private int age;

	public Person(String name, int age) {
		this.name = name;
		this.age = age;
	}

	public String toString() {
		return "  ：" + this.name + "，  ：" + this.age;
	}

	public String getName() {
		return name;
	}

	public int getAge() {
		return age;
	}
}

Personクラスは開発が完了し、パッケージ化されてクライアントに渡されましたが、その後、オブジェクト配列のソートが必要になります.この場合、Personクラスは変更できないため、java.util.Comparatorインタフェースという別の比較器しか使用できません.このインタフェースは以下のように定義されています.

public interface Comparator {
	public int compare(T o1, T o2);
	public boolean equals(Object obj);
}

例:特別な比較ルールの定義

class PersonComparator implements Comparator {
	@Override
	public int compare(Person o1, Person o2) {
		if (o1.getAge() > o2.getAge()) {
			return -1;
		} else if (o1.getAge() < o2.getAge()) {
			return 1;
		}
		return 0;
	}
}

このようなサービスはPersonクラスにしか提供できません.次に、ソートするときにArraysクラスで次の方法があります.

ソート:public static void sort(T[]a,Comparator)

hdu 1266

JAva処理は2つの配列の共通値を除去する