算法筆記：自定義排序 Comparator

在做算法題時經常需要排序，java提供Arrays.sort()，但是預設隻能從小到大排序一維數組，如果想排序二維數組，或者自定義排序規則：從小到大、字元串排序規則等，需要傳入Comparator接口并實作裡面的compare方法。

compare方法

傳回值int

參數：T o1,T o2

傳回正數則正序，否則逆序。

例1：從大到小排序

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;

public class Sort {
    @Test
    public void comparator1(){
        Integer[] arr={1,2,1,3,4,8,7};
        Arrays.sort(arr,new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;//從大到小 快排 如果是o1-o2從小到大
            }
        });
        for (int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
}
           

必須是對包裝類數組或者多元數組自定義排序，int沒辦法自定義排序。

o1-o2>0,則交換兩個數，否則不變，同理o2-o1你可以在紙上畫一畫，試一下，注意不是快排！（之前寫的快排，糾正，對于非基本類型不是快排，sort自動選擇用插入排序或歸并排序看哪個效率高）。

【宮水三葉の相信科學系列】為什麼根據「拼接結果的字典序大小」決定「其在序列裡的相對

例2：對二維數組排序

public void comparator2(){
        int[][] arr={{1,2},{2,3},{3,4},{1,3}};
        Arrays.sort(arr,new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];//按下标1的大小排序 從小到大
            }
        });
        for (int i=0;i<arr.length;i++){
            for(int j=0;j<arr[0].length;j++) {
                System.out.print(arr[i][j] + " ");
            }
        }
    }
           

參考題目：leetcode435 無重疊區間

例3：對字元串排序compareTo

public void comparator3(){
        String[] arr={"10","11","3","0","5"};
        Arrays.sort(arr,new Comparator<String>(){
            @Override
            public int compare(String o1, String o2) {
                return (o2+o1).compareTo(o1+o2);//從大到小排 例："510" "105"傳回正值交換
            }
        });
        for (int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
           

compareTo作用： 傳回參與比較的前後兩個字元串的asc碼的內插補點，如果兩個字元串首字母不同，則該方法傳回首字母的asc碼的內插補點。

參考題目：LeetCode179 最大數

對大數排序

有大數的時候不要用減号，用大于、小于就好了，不然越界！

public void comparator2(){
        int[][] arr={{1,2},{2,3},{3,4},{1,3}};
        Arrays.sort(arr,new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1]>=o2[1])
                    return 1;
                else return -1;
                //按下标1的大小排序 從小到大
            }
        });
        for (int i=0;i<arr.length;i++){
            for(int j=0;j<arr[0].length;j++) {
                System.out.print(arr[i][j] + " ");
            }
        }
    }
           

參考題目：LeetCode452. 用最少數量的箭引爆氣球

可以自測一下

劍指 Offer 45. 把數組排成最小的數

參考

常見的接口與類 – Comparator

Comparator的compare方法如何定義升序降序（源碼角度）

LeetCode題目