一、Java对象的比较
1、比较对象的几种方法:
上一篇文章我们介绍了【优先级队列】，即PriorityQueue，其实，优先级队列在插入元素中有一个要求：插入的元素不能是null或者元素之间必须要能够进行比较，为了简单起见，我们只是插入了Integer类型的数据。
那么优先级队列能不能插入自定义的类型对象呢？ 如果能，他又该如何比较该对象的大小，对其进行排序呢？
答：优先级队列可以插入自定义类型的对象！让我举例来解决这个问题！
我们先自定义一个Card类型（卡牌类），然后在main方法中实例化一个PriorityQueue队列p，
给该队列添加两个元素，这两个元素是Card对象！
运行程序，我们发现，程序抛出错误，原因是：该队列每次添加元素时，会对队列中元素进行排序，使其成为一个【小根堆】，那么，每次排序时都需要对元素之间【进行比较】，这里有一个问题：Card类型的对象该如何比较？比较的依据是什么？这些问题程序也不知道怎么做，因此会抛出错误！
这个问题其实在上一篇文章【优先级队列】已经介绍过，只需要自定义实现一个【比较器】然后将这个比较器作为参数传入【队列】的构造函数中即可！
那么，我们先来探究一下，以该Card对象为例，对象之间该如何比较？
【方法1】：用双等号来比较？
假想一下，数值相同是数字可以用双等号来判断值是否相同！那么，对象是否也可以呢？
首先，我们实例化两个Card对象c1和c2；这两个对象的rank和suit都相同，那么，我们看看，打印一下c1==c2的结果
很遗憾，结果为false，c1与c2不同，这是因为c1和c2代表的只是【对象的引用】，好比一栋小区的同种类型的房间，内部的结构相同，可是【房间号】不同，而c1和c2的地位就类似于【房间号】，所以用【双等号】是无法比较对象类型是否相同的！
【方法2】：使用equals方法
我们都知道，每个对象的类型都默认继承【Object类】，可以说【Object类】是所有类型的【父类】，那么当然，它也是【Card类】的【父类】，这个Object类中里面有这么一个方法equals，它是来比较类型是否相同的方法！
那么我们在【Card类】中重写该方法 ，写出我们比较这个【Card类】的具体依据：是根据【卡牌值rank】和【卡牌花色suit】来判断两个卡牌对象是否相同？
//自定义一个【卡牌类】
class Card {
//成员变量
public int rank;//数值
public String suit;//花色
//构造方法
public Card(int rank,String suit){
this.rank=rank;
this.suit=suit;
}
//重写equals方法
@Override
public boolean equals(Object obj) {
//自己和自己比较.,如c1.equals(c1)
if(this==obj){
return true;
}
//如果obj不是Card类，如c1.equals(new Student())
if(obj==null||!(obj instanceof Card)){
return false;
}
Card c=(Card)obj;
return this.rank==c.rank&&this.suit==c.suit;
}
}
让我们调用一下该方法看看能否比较c1和c2？ 结果为true，证明该方法可以以rank和suit为依据比较两个卡牌对象！
重写equals方法的方式虽然可以比较两个对象的大小，但缺陷是，equals只能按照相等进行比较，不能按照大于、小于的方式进行比较！那么，我们需要学习另外一种方法，基于Comparable接口类的比较！
【方法3】：基于Compareable接口类的比较
Comparble是JDK提供的泛型的比较接口类，源码实现如下：
public interface Comparable<E>{
//比较泛型类的方法
int compareTo(E o);
//返回值：
//<0 ：表示this指向的对象小于o指向的对象
//=0 ：表示this指向的对象等于o指向的对象
//>0 : 表示this指向的对象大于o指向的对象
}当我们自定义一个类型时（如Card类），如果想要按照大小的方式进行比较时：可以在定义类时，实现Comparble接口即可，然后在该类中重写campareTo方法。
//自定义一个【卡牌类】
class Card implements Comparable<Card>{//实现Comparable接口
//成员变量
public int rank;//数值
public String suit;//花色
//构造方法
public Card(int rank,String suit){
this.rank=rank;
this.suit=suit;
}
//重写compareTo方法：根据卡牌值比较两个对象大小
@Override
public int compareTo(Card o) {
return this.rank-o.rank;
}
}
代码运行：
如图，调用一下compareTo方法，比较一下两张卡牌，程序运行打印出1，说明c1大于c2；
【方法4】:基于比较器的比较
前面的方法虽然好，但是也有一个缺点，就是，我们只能通过单一的方法对两个对象进行比较，其实，对两个对象的比较也可以根据其他成员变量的内容进行比较，那么单单通过一个compareTo方法就显得不够用了；
举例来说：我们定义一个学生类：创建学生A和学生B，我们希望可以比较一下两个对象的大小，即可以从四个方面来讨论，分别为年龄、年级、身高、体重，这都可以成为我们比较对象大小的依据，此时，只通过compareTo方法来比较学生类，就会显得不灵活！因为它一次只能通过某一种具体的判断依据来比较对象的大小！
class Student{
//成员变量
public int age; //年龄
public int grade; //年级
public int height; //身高
public int weight; //体重
}由此，我们来学习另外一种灵活的比较方法：基于【比较器】的比较
比较器源码：
class 比较器名 implements Comparator<要比较对象的类名E>{
//重写compare方法
public int compare(E o1,E o2){
//……具体比较方式自己写
}
}//1、自定义一个学生类
public class Student {
//成员变量
public int age;
public int grade;
public int height;
public int weight;
//构造方法
public Student(int age,int grade,int height,int weight){
this.age=age;
this.grade=grade;
this.height=height;
this.weight=weight;
}
}
//2、实现比较器
//年龄比较器
class AgeComparator implements Comparator<Student>{
@Override
public int compare(Student o1, Student o2) {
return o1.age-o2.age;
}
}
//年级比较器
class GradeComparator implements Comparator<Student>{
@Override
public int compare(Student o1, Student o2) {
return o1.grade-o2.grade;
}
}
//升高比较器
class HeightComparator implements Comparator<Student>{
@Override
public int compare(Student o1, Student o2) {
return o1.height-o2.height;
}
}
//体重比较器
class WeightComparator implements Comparator<Student>{
@Override
public int compare(Student o1, Student o2) {
return o1.weight-o2.weight;
}
}
//3、根据比较依据使用比较器
class test{
public static void main(String[] args) {
Student studentA=new Student(10,6,70,160);
Student studentB=new Student(12,8,60,170);
//实例化年龄比较器
AgeComparator ageComparator=new AgeComparator();
System.out.println(ageComparator.compare(studentA,studentB));
//实例化年级比较器
GradeComparator gradeComparator=new GradeComparator();
System.out.println(gradeComparator.compare(studentA,studentB));
//实例化生高比较器
HeightComparator heightComparator=new HeightComparator();
System.out.println(heightComparator.compare(studentA,studentB));
//实例化体重比较器
WeightComparator weightComparator=new WeightComparator();
System.out.println(weightComparator.compare(studentA,studentB));
}
}
2、给数组的每一个元素排序并且打印
//自定义一个【卡牌类】
class Card implements Comparable<Card>{//实现Comparable接口
//成员变量
public int rank;//数值
public String suit;//花色
//构造方法
public Card(int rank,String suit){
this.rank=rank;
this.suit=suit;
}
//重写compareTo方法：
@Override
public int compareTo(Card o) {
return this.rank-o.rank;
}
//重写equals方法
@Override
public boolean equals(Object obj) {
//自己和自己比较.,如c1.equals(c1)
if(this==obj){
return true;
}
//如果obj不是Card类，如c1.equals(new Student())
if(obj==null||!(obj instanceof Card)){
return false;
}
Card c=(Card)obj;
return this.rank==c.rank&&this.suit==c.suit;
}
//重写toString方法
@Override
public String toString() {
return "Card{" +
"rank=" + rank +
", suit='" + suit + '\'' +
'}';
}
}
//实现一个RankComparator比较器
class RankComparator implements Comparator<Card>{
@Override
//o2-o1
public int compare(Card o1, Card o2) {
return o2.rank-o1.rank;
}
}
public class Test {
public static void main(String[] args) {
//给数组中每一个元素排序并且打印
Card[] cards=new Card[3];
cards[0]=new Card(1,"红桃");
cards[1]=new Card(9,"红桃");
cards[2]=new Card(6,"红桃");
//基于Compareable接口类的比较
Arrays.sort(cards);
System.out.println(Arrays.toString(cards));
//基于比较器的比较
Arrays.sort(cards,new RankComparator());
System.out.println(Arrays.toString(cards));
}
}
二、排序算法
所谓的排序，就是使一串记录，按照递增或者递减排列起来。
接下来，让我们来了解一下几种常见的排序算法！
1、直接插入排序
【基本思想】
把待排序的记录按照其【关键码值】的大小逐个插入到一个【已经排好序】的有序列表中，直到所有的记录插入完为止，得到一个新的有序序列！
举个例子说明：假如给一个数组：10 、6 、4 、3 、7，要求按照从小到大排列！
1、首先，从第一个元素开始，认为该元素已经被排好序
2、取下一个元素，将这个元素的值【存入】tmp中，往前遍历前面的元素
3、如果前面的元素的值【大于】tmp的值，那么该元素向后移动一位
4、重复该操作，直至找到某个元素【小于或者等于】tmp，将tmp存入该元素的下一个位置
5、如果遍历结束，发现前面的元素都【大于】tmp，那么将tmp插入到下标为0的位置
【动画展示】
我们将【i】下标的元素存入tmp中，然后再通过【j】来遍历下标为【i】之前的元素，如果发现 【j】 下标的元素【大于】tmp，那么将该元素移动到下一位！当【i】超过数组下标的最大值，排序结束！
第一次：
第二次：
第三次：
第四次：
【 代码实现】
//插入排序
public static void insertSort(int[] array){
for(int i=1;i<array.length;i++){
int j=0;
int tmp=array[i];
for(j=i-1;j>=0;j--){
if(array[j]>tmp){
array[j+1]=array[j];
}else{
break;
}
}
array[j+1]=tmp;
}
}2、希尔排序
【基本思想】
通过上面【直接插入排序】的学习，其实我们很容易知道，如果一个序列越趋于【有序】，那么插入排序的效率是越高的，如果想不明白，你可以拿着一个【完全逆序】的序列和一个【已经有序】的序列，走一遍【直接插入排序】，看看哪一个步骤比较少！显而易见，越趋于有序步骤越少，那么，下面的希尔排序，正是运用了这个思想：
先使序列趋于有序化！减少直接插入排序的步骤！从而提高了直接插入排序的效率！那么该如何做呢？
首先，将一组【序列】均分为几组【序列】，先分别对每一组【序列】进行一遍【直接插入排序】。那么，相比于之前的序列，排序后的序列比之前更加有序了。
接着，减少分组的组数，将序列继续均分为几组序列，再对每组序列进行【直接插入排序】。
以此类推，继续减少组数，分组，排序，直至最后分组的组数为1，进行【直接插入排序】，那么该序列就已经有序了！
【排序分组】
那么现在，又有一个问题，该如何分组，才比较好呢？或许有人会这么想，临近的数据分组。我们来分析一下。
首先，我们分组希望得到这样一个结果，那么就是【尽量使大的元素往后靠，小的元素往前靠】，那么这样分组明显是达不到我们要的效果的！比如第一组的【9】 和【1】，分组之后【9 】仍然在靠前的位置！
因此，我们需要考虑另外一种更加好的分组方式！比如，跳跃分组！每一组的间隔即为分组的组数，这样它就满足了【大元素往后靠，小元素往前靠】的要求！
【动画展示】
第一次排序：
组数=元素个数/2=5
第二次排序：
组数=原来组数/2=2
第三次排序
组数=原来组数/2=1
这里也就是最后一次排序，原理相同，不再展示了！
【代码实现】
//希尔排序
public static void shellSort(int [] array){
//1\第一次的组数=元素个数/2
int gap= array.length/2;
//2\循环结束的条件是组数为0
while(gap>=1){
insertSort(gap,array);
gap=gap/2;
}
}
//改良版的【直接插入排序】
public static void insertSort(int gap,int [] array){
//注意，这里排序的过程并不是像动画展示那样分别排序，它的排序过程是交替进行的
//如果不理解，可按照代码逻辑演示一遍
for(int i=gap;i<array.length;i++){
int j=i-gap;
int tmp=array[i];
for(;j>=0;j=j-gap){
if(array[j]>tmp){
array[j+gap]=array[j];
}else{
break;
}
}
array[j+gap]=tmp;
}
}3、直接选择排序
【基本思想】
假设一个数组共有n个元素；
第一次，令【i】为0，在array[i]---->array[n-1] 的元素中，找出最小的【元素】，让该最小元素与array[i]交换！
第二次，令i++；重复上述操作，直至i==n-1；
【动画展示】
该排序过程使用【j】来遍历【i】下标之后的元素，将元素最小值的下标存入【minIndex】中，每次【j】遍历结束，交换array[i]和array[minIndex]
【代码实现】
//选择排序
public static void select(int [] array){
for(int i=0;i<array.length;i++){
int j=i+1;
int minIndex=i;
for(;j< array.length;j++){
if(array[j]<array[minIndex]){
minIndex=j;
}
}
swap(array,i,minIndex);//交换元素
}
}
//交换元素
public static void swap(int [] array,int i,int j){
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
4、冒泡排序
【基本思想】
每次比较相邻两个元素的值，将小元素置于大元素之前，这样，通过第一轮遍历数组后，可以将最大元素置于数组末尾。
再次重复上述操作，将倒数第二大的元素置于倒数第二个位置！
以此类推……
【动画展示】
【代码实现】
//冒泡排序
public static void bubbleSort(int [] array){
//外层循环：冒泡排序的趟数(元素个数-1）
for(int i=1;i<=array.length-1;i++){
//内层循环：需要遍历元素的个数
for(int j=0;j<=array.length-1-i;j++){
//将大元素置于小元素之后
if(array[j]>array[j+1]){
swap(array,j,j+1);
}
}
}
}
//交换元素
public static void swap(int [] array,int i,int j){
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
6、快速排序
【基本思想】
【快速排序】是一种利用递归算法的排序！ 通过多次调用同一个方法，将一个大的序列的排序看作一个个子序列的排序，通过子序列的不断排序，最终使大序列有序！
下面就举一个例子，来阐述一下快速排序的原理！
假设我们要排列以下序列，首先，先规定一个【基准元素】，使用P来代表【基准元素的下标】默认该元素为【数组的最左边元素】，起初，使用L和R分别代表数组的【最左边下标】和【最右边下标】
1、在【L<R】的前提下，先使用R找到小于【基准元素】的元素下标，再使用L找到大于【基准元素的元素下标；
2、各自找到下标后，交换下标为R和L的元素，最后，直至R==L，交换下标为P和下标为L（或者R）的元素！
3、经历过一次这样的排序过后，可以取得这样的效果：
即【基准元素】会分割整个序列，使得【基准元素】前的元素都是小于或者等于【基准元素】，【基准元素】之后的元素都大于或者等于【基准元素】
4、再将基准元素之前的序列和基准元素之后的序列 看作两个【子序列】，各自重复进行1、2操作，直至整个序列有序！
【动画展示】
【代码实现】
//快速排序
public static void quickSort(int [] array,int start,int end){
if(start>end){
return;
}
int parIndex=partition(array,start,end);
quickSort(array,start,parIndex-1);
quickSort(array,parIndex+1,end);
}
//以基准元素分割序列
public static int partition(int [] array,int left,int right){
int par=array[left];
int i=left;//记录par的下标
while(left<right){
//一定要先找右边！！！
//在右边找到【小于】par的元素下标
while (left<right&&array[right]>=par){
right--;
}
//在左边找到【大于】par的元素下标
while (left<right&&array[left]<=par){
left++;
}
//此时left<right或者left==right
swap(array,left,right);
}
swap(array,i,left);
return left;
}
//交换元素
public static void swap(int [] array,int i,int j){
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
7、归并排序
【基本思想】
归并排序的排序思路整体分为两个步骤：【分序】和【合序】。
也就是：先将一个【大的序列】分割为一个个【单独的元素】，然后再将【元素】合并为【小的有序序列】，再将这些【小的有序序列】合并为一个【大的有序序列】！
【分序】
数组的分序是通过递归实现的，首先，我们需要使用L和R，分别代表数组的【最左边】下标和【最右边】下标！使用mid代表【（L+R）/ 2】的下标
然后再根据【mid】分割序列，将数组分割为【L——>mid】的左序列和【mid+1——>R】的右序列，再分别给左序列和右序列定义新的R、L、mid，重复上述操作！直至L>=R，分割序列结束
【合序】
在【分序】操作中，一个序列会被分割为【左序列】和【右序列】，那么合序的操作就是依次将匹配的左右序列按照【有序序列】合并！
因此，这里使用了s1，e1和s2，e2分别代表左右序列的起始下标和终止下标，每次比较左右序列起始下标的元素大小，将小的元素放在创建好的临时数组中，直至s1和s2都等于各自的终止下标，才算合序结束！
这样，通过多次左右序列的合序，最终整个数组趋于有序！
【代码实现】
//归并排序
public static void mergeSort(int []array,int left,int right){
//当最左边下标大于或者等于最右边下标，递归结束
if(left>=right){
return;
}
//分序
int mid=(left+right)/2;
mergeSort(array,left,mid);//左序列
mergeSort(array,mid+1,right);//右序列
//合并左序列和右序列
merge(array,left,right,mid);
}
//合并序列并且拷贝到原数组中
public static void merge(int[] array,int left,int right,int mid){
//创建一个临时数组合并两个【小序列】元素
int [] tmp=new int[right-left+1];
int s1=left;
int e1=mid;
int s2=mid+1;
int e2=right;
int k=0;
while (s1<=e1&&s2<=e2){
if(array[s1]<array[s2]){
tmp[k++]=array[s1++];
}else {
tmp[k++]=array[s2++];
}
}
while(s1<=e1){
tmp[k++]=array[s1++];
}
while (s2<=e2){
tmp[k++]=array[s2++];
}
//将排好序的数组拷贝到原数组
for(int i=0;i<tmp.length;i++){
array[i+left]=tmp[i];//这一步的代码建议通过【调试】自行去理解，因为不好解释
}
}