Java中的排序與內(nèi)部比較器Compareable解析

更新時(shí)間：2023年11月07日 10:12:52 作者：JFS_Study

這篇文章主要介紹了Java中的排序與內(nèi)部比較器Compareable解析,一般沒(méi)有特殊要求時(shí),直接調(diào)用(底層默認(rèn)的升序排列)就可以得到想要的結(jié)果,所謂的 sort 方法排序底層都是基于這兩種排序,故如果需要設(shè)計(jì)成所想要的排序就需要了解底層排序原理,需要的朋友可以參考下

一、Arrays.sort() 與 Collections.sort() 排序

Arrays.sort() 可以對(duì)數(shù)組，字符串等排序

import java.util.Arrays;
 
public class sort {
  public static void main(String[] args) {
    int[] num = new int[]{3,2,4,1,5};
    Arrays.sort(num);
    for(int i=0;i<num.length;i++) {
      System.out.print(num[i]+" ");
    }
  }
}
//1 2 3 4 5

Collections.sort() 是對(duì)list集合排序，list 也可以放數(shù)字、字符串

import java.util.ArrayList;
import java.util.Collections;
 
public class sort {
  public static void main(String[] args) {
    ArrayList<Integer> list  = new ArrayList<>();
    list.add(3);
    list.add(2);
    list.add(1);
    Collections.sort(list);
    System.out.print(list);
  }
}
//[1, 2, 3]

一般沒(méi)有特殊要求時(shí)，直接調(diào)用(底層默認(rèn)的升序排列)就可以得到想要的結(jié)果。所謂的 sort 方法排序底層都是基于這兩種排序，故如果需要設(shè)計(jì)成所想要的排序就需要了解底層排序原理。對(duì)自定義對(duì)象數(shù)組排序，需要引入“比較器”的概念。Compareable 和 Compartor 接口就是比較器抽象接口，通過(guò)實(shí)現(xiàn)類(lèi)重寫(xiě)接口方法來(lái)進(jìn)行對(duì)象比較。

二、內(nèi)部比較器：Compareable 接口分析

當(dāng)使用 sort(Objetc[] a) 來(lái)進(jìn)行對(duì)象的自然排序時(shí)，該對(duì)象必需實(shí)現(xiàn) Compareable 接口，重寫(xiě) compareTo 方法，并一般在此方法中定義 3 種返回值(正，零，負(fù))來(lái)進(jìn)行排序標(biāo)準(zhǔn)的確認(rèn)，一般默認(rèn)下面值來(lái)表示：

return 1 時(shí)，按照升序。
return 0 時(shí)，原位置不動(dòng)。
return -1 時(shí)，按照降序。

應(yīng)用：目標(biāo)類(lèi)實(shí)現(xiàn) Comparable 接口，重寫(xiě) compareTo()，定義排序規(guī)則，就可以直接調(diào)用 Collections.sort() 來(lái)排序?qū)ο髷?shù)組。

@Data
public class Student implements Comparable{
    private int id;
    private int age;
    private int height;
    private String name;
    public Student(int id, String name, int age, int height) {
        this.id = id;
        this.name = name;
        this.age = age;
        this.height = height;
    }
    @Override
    public int compareTo(Object o) {
        Student s = (Student) o;
        if (this.age > s.age) {
            return 1;
        }else if (this.age < s.age) {
            return -1;
        }else {
            if (this.height >= s.height) {
                return 1;
            }else {
                return -1;
            }
        }
    }
}

上面是實(shí)現(xiàn)升序排列，如果要實(shí)現(xiàn)降序只需要把 1 與 -1 互換位置即可。測(cè)試：

public class Test {
	public static void printData(List<Student> list) {
		for (Student student : list) {
			System.out.println("學(xué)號(hào):"+student.getId()+"姓名:"+student.getName()+
"年齡"+student.getAge()+"身高:"+student.getHeight());
		}
	}
	public static void main(String[] args) {
		List<Student> list = new ArrayList<>();
		list.add(new Student(1, "A", 20, 180));
		list.add(new Student(2, "B", 21, 175));
		list.add(new Student(3, "C", 22, 190));
		list.add(new Student(4, "D", 21, 170));
		list.add(new Student(5, "E", 20, 185));
		System.out.println("before sorted");
		printData(list);
		Collections.sort(list);
		System.out.println("after age and height sorted");
		printData(list);
	}
}

結(jié)果：

before sorted
學(xué)號(hào):1姓名:A年齡20身高:180
學(xué)號(hào):2姓名:B年齡21身高:175
學(xué)號(hào):3姓名:C年齡22身高:190
學(xué)號(hào):4姓名:D年齡21身高:170
學(xué)號(hào):5姓名:E年齡20身高:185
after age and height sorted
學(xué)號(hào):1姓名:A年齡20身高:180
學(xué)號(hào):5姓名:E年齡20身高:185
學(xué)號(hào):4姓名:D年齡21身高:170
學(xué)號(hào):2姓名:B年齡21身高:175
學(xué)號(hào):3姓名:C年齡22身高:190

三、Compartor 接口分析

①先建一個(gè)基本屬性類(lèi)：

@Data
public class Student {
    //創(chuàng)建兩個(gè)基本屬性
    String name = "";
    int age = 0;
    //重寫(xiě)構(gòu)造方法用來(lái)傳遞數(shù)據(jù)
    public Student(String name, int age) {
       super();
       this.name = name;
       this.age = age;
    }
}

創(chuàng)建按照姓名升序排列的實(shí)現(xiàn)類(lèi) ：

import java.util.Comparator;
//按照名字的升序排列。實(shí)現(xiàn)接口，泛型是自定義類(lèi)，里面有要排序的內(nèi)容   
public class NameSort implements Comparator{
    @Override  
    //兩個(gè)參數(shù)是泛型的對(duì)象
    public int compare(Student o1, Student o2) {
   //按照姓名的升序排列，前面加個(gè)負(fù)號(hào)就按照降序排列
       return o1.getName().compareTo(o2.getName());
    }
}

②直接定義Java中PriorityQueue優(yōu)先級(jí)隊(duì)列就是利用這原理：

//傳進(jìn)來(lái)的數(shù)組或是字符串以及集合list
Arrays.sort(num,new Comparator<String>(){
    @Override
    public int compare(String o1,String o2){
        return o1.compareTo(o2);//升
        //return o2.compareTo(o1);//降
    }
});

應(yīng)用：實(shí)現(xiàn)比較器接口 Comparator，重寫(xiě) compare 方法，直接當(dāng)做參數(shù)傳進(jìn) sort 中。

@Data
public class Student {
	private int id;
	private int age;
	private int height;
	private String name;
	public Student(int id, String name, int age, int height) {
		this.id = id;
		this.name = name;
		this.age = age;
		this.height = height;
	}
}

測(cè)試：

public class Test {
	public static void main(String[] args) {
		List<Student> list = new ArrayList<>();
		list.add(new Student(1, "A", 20, 180));
		list.add(new Student(2, "B", 21, 175));
		list.add(new Student(3, "C", 22, 190));
		list.add(new Student(4, "D", 21, 170));
		list.add(new Student(5, "E", 20, 185));
		System.out.println("before sorted");
		printData(list);
		Collections.sort(list, new Comparator<Student>() {
			@Override
			public int compare(Student o1, Student o2) {
				if(o1.getAge() >= o2.getAge()) {
					return 1;
				}
				else {
					return -1;
				}
			}
		});
		System.out.println("after age sorted");
		printData(list);
		Collections.sort(list, new Comparator<Student>() {
			@Override
			public int compare(Student o1, Student o2) {
				if(o1.getAge() > o2.getAge()) {
					return 1;
				}else if (o1.getAge() < o2.getAge()){
					return -1;
				}else {
					if (o1.getHeight() >= o2.getHeight()) {
						return 1;
					}else {
						return -1;
					}
				}
			}
		});
		System.out.println("after age and height sorted");
		printData(list);
	}
	public static void printData(List<Student> list) {
		for (Student student : list) {
			System.out.println("學(xué)號(hào):"+student.getId()+"姓名:"+student.getName()+
"年齡"+student.getAge()+"身高:"+student.getHeight());
		}
	}
}

輸出結(jié)果：

before sorted
學(xué)號(hào):1姓名:A年齡20身高:180
學(xué)號(hào):2姓名:B年齡21身高:175
學(xué)號(hào):3姓名:C年齡22身高:190
學(xué)號(hào):4姓名:D年齡21身高:170
學(xué)號(hào):5姓名:E年齡20身高:185
after age sorted
學(xué)號(hào):1姓名:A年齡20身高:180
學(xué)號(hào):5姓名:E年齡20身高:185
學(xué)號(hào):2姓名:B年齡21身高:175
學(xué)號(hào):4姓名:D年齡21身高:170
學(xué)號(hào):3姓名:C年齡22身高:190
after age and height sorted
學(xué)號(hào):1姓名:A年齡20身高:180
學(xué)號(hào):5姓名:E年齡20身高:185
學(xué)號(hào):4姓名:D年齡21身高:170
學(xué)號(hào):2姓名:B年齡21身高:175
學(xué)號(hào):3姓名:C年齡22身高:190

單從上面的例子可以看出排序是穩(wěn)定的，查看 Java 的Collections.sort的源代碼，確實(shí)是基于穩(wěn)定的歸并排序?qū)崿F(xiàn)的，內(nèi)部還做了優(yōu)化，叫TimSort。

API 排序

public static void main(String[] args) {

    List<Student> stuList = new ArrayList<>();
    stuList.add(new Student(1, "A", 20, 180));
    stuList.add(new Student(2, "B", 21, 175));
    stuList.add(new Student(3, "C", 22, 190));
    stuList.add(new Student(4, "D", 21, 170));
    stuList.add(new Student(5, "E", 20, 185));

    System.out.println(stuList);

    System.out.println("-------------先年齡升---后身高升-------------");
    Comparator<Student> compareAge = Comparator.comparing(Student::getAge);
    Comparator<Student> compareHight = Comparator.comparing(Student::getHeight);
    Collections.sort(stuList, compareAge.thenComparing(compareHight));
    for (Student s : stuList) {
        System.out.println(s.getName() + "," + s.getAge() + "," + s.getHeight());
    }

    System.out.println("-------------先年齡升---后身高降-------------");
    Collections.sort(stuList, compareAge.thenComparing(compareHight.reversed()));
    for (Student s : stuList) {
        System.out.println(s.getName() + "," + s.getAge() + "," + s.getHeight());
    }

    System.out.println("-------------先年齡降---后身高降-------------");
    Collections.sort(stuList, compareAge.reversed().thenComparing(compareHight.reversed()));
    for (Student s : stuList) {
        System.out.println(s.getName() + "," + s.getAge() + "," + s.getHeight());
    }
}

輸出結(jié)果：

[Student(id=1, age=20, height=180, name=A), Student(id=2, age=21, height=175, name=B), Student(id=3, age=22, height=190, name=C), Student(id=4, age=21, height=170, name=D), Student(id=5, age=20, height=185, name=E)]
-------------先年齡升---后身高升-------------
A,20,180
E,20,185
D,21,170
B,21,175
C,22,190
-------------先年齡升---后身高降-------------
E,20,185
A,20,180
B,21,175
D,21,170
C,22,190
-------------先年齡降---后身高降-------------
C,22,190
B,21,175
D,21,170
E,20,185
A,20,180
Process finished with exit code 0

四、compareTo 源碼說(shuō)明

String比較用 compareTo 方法，針對(duì)參與比較的不同的字符，從第一位開(kāi)始往后比較，然后返回相應(yīng)的 int 值：

字符個(gè)數(shù)相同，返回參與比較的前后兩個(gè)字符串的 ASSIC 碼差值。
兩個(gè)字符串首字母不同，則該方法返回首字母的 ASSIC 碼差值。
參與比較的兩個(gè)字符串如果首字符相同，則比較下一個(gè)字符，直到有不同的為止，返回該不同的字符的 ASSIC 碼差值。
兩個(gè)字符串不一樣長(zhǎng)，可以參與比較的字符又完全一樣，則返回兩個(gè)字符串的長(zhǎng)度差值。
目前 compareTo 項(xiàng)目中的用途是比較版本號(hào)的高低。

private final char value[]; 
public int compareTo(String anotherString) {
     int len1 = value.length;
     int len2 = anotherString.value.length;
     int lim = Math.min(len1, len2);
     char v1[] = value;
     char v2[] = anotherString.value;

     int k = 0;
     while (k < lim) {
         char c1 = v1[k];
         char c2 = v2[k];
         if (c1 != c2) {
             return c1 - c2;
         }
         k++;
     }
     return len1 - len2;
}

Java 中的 compareto 方法實(shí)例

public static void main(String[] args) {
      //返回參與比較的前后兩個(gè)字符串的ASSIC碼的差值
       String a = "a";//97
       String b = "b";//98
       System.out.println("a.compareTo(b)：" + a.compareTo(b));//-1
       System.out.println("b.compareTo(a)：" + b.compareTo(a));//1

       String c = "c";
       String c1 = "c";
       System.out.println("c.compareTo(c1)：" + c.compareTo(c1));//0

       //兩個(gè)字符串首字母不同，則該方法返回首字母的ASSIC碼的差值
       String d = "abc";
       String e = "bcdfg";
       System.out.println("d.compareTo(e)：" + d.compareTo(e));//-1

       //參與比較的兩個(gè)字符串如果首字符相同，則比較下一個(gè)字符，
       //直到有不同的為止，返回該不同的字符的ASSIC碼差值
       String g = "abedfg";
       System.out.println("d.compareTo(g)：" + d.compareTo(g));//-2
       //兩個(gè)字符串不一樣長(zhǎng)，可以參與比較的字符又完全一樣，
       //則返回兩個(gè)字符串的長(zhǎng)度差值
       String h = "abcdefg";
       System.out.println("d.compareTo(h)：" + d.compareTo(h));//-4
       String i = "ab";
       System.out.println("d.compareTo(i)：" + d.compareTo(i));//1
       //目前compareTo項(xiàng)目中的用途是比較版本號(hào)的高低
       String num = "1.0.0";
       String val = "1.0.1";
       System.out.println("num.compareTo(val)：" + num.compareTo(val));//-1
  }

結(jié)果如下：

面試

輸入一個(gè)正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來(lái)排成一個(gè)數(shù)，打印能拼接出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{3，32，321}，則打印出這三個(gè)數(shù)字能排成的最小數(shù)字為321323。

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        if(numbers.length==0) {
            return "";
        }
        int len = numbers.length;
        String[] str = new String[len];
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<len;i++) {
            str[i] = String.valueOf(numbers[i]);
        }
        Arrays.sort(str,new Comparator<String>(){
            @Override
            public int compare(String o1,String o2){
                String c1 = o1 + o2;
                String c2 = o2 + o1;
                return c1.compareTo(c2);
            }
        });
        for(int i=0;i<len;i++) {
            sb.append(str[i]);
        }
        return sb.toString();
    }
}

到此這篇關(guān)于Java中的排序與內(nèi)部比較器Compareable解析的文章就介紹到這了,更多相關(guān)Java中的排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: