java如何給物件按照字串屬性進行排序

2022-11-17 14:00:03

給物件按照字串屬性進行排序

在java中物件進行排序，排序的屬性是string，我們只需要實現Comparator介面，然後實現比較的方式。

public class StringSort {
    public static void main(String[] args) {

        test1();

    }

    // 方式1：
    public static void test1(){
        JSONObject jsonObject = JSONObject.parseObject("{"result":[{"id":"A1001","text":"程式設計師"}, {"id":"G1003","text":"建築師"}, {"id":"D1005","text":"設計師"}, {"id":"G1009","text":"自由職業"}, {"id":"E2007","text":"學生"}, {"id":"C1009","text":"教師"}, {"id":"A1002","text":"醫生"}, {"id":"B1005","text":"律師"}, {"id":"F2009","text":"架構師"}]}");
        List<JSONObject> list = JSONArray.parseArray(jsonObject.getString("result"), JSONObject.class);

        list.forEach(System.out::println);

        Collections.sort(list, new Comparator<JSONObject>() {
            @Override
            public int compare(JSONObject o1, JSONObject o2) {
                 return  o1.getString("id").compareTo(o2.getString("id") ); // 升序排列
//                return  - o1.getString("id").compareTo(o2.getString("id") ); // 降序排列
            }
        });

        System.out.println("--------------排序後--------------------");

        list.forEach(System.out::println);
    }

    // 方式2：
    public  static void test2(){
        JSONObject jsonObject = JSONObject.parseObject("{"result":[{"id":"A1001","text":"程式設計師"}, {"id":"G1003","text":"建築師"}, {"id":"D1005","text":"設計師"}, {"id":"G1009","text":"自由職業"}, {"id":"E2007","text":"學生"}, {"id":"C1009","text":"教師"}, {"id":"A1002","text":"醫生"}, {"id":"B1005","text":"律師"}, {"id":"F2009","text":"架構師"}]}");
        List<JSONObject> list = JSONArray.parseArray(jsonObject.getString("result"), JSONObject.class);

        list.forEach(System.out::println);

        Collections.sort(list, (o1, o2) -> {
            // return   o1.getString("id").compareTo(o2.getString("id") ); // 升序排列
            return  - o1.getString("id").compareTo(o2.getString("id") ); // 降序排列
        });

        System.out.println("--------------排序後--------------------");

        list.forEach(System.out::println);
    }

    // 方式3：
    public  static void test3(){
        JSONObject jsonObject = JSONObject.parseObject("{"result":[{"id":"A1001","text":"程式設計師"}, {"id":"G1003","text":"建築師"}, {"id":"D1005","text":"設計師"}, {"id":"G1009","text":"自由職業"}, {"id":"E2007","text":"學生"}, {"id":"C1009","text":"教師"}, {"id":"A1002","text":"醫生"}, {"id":"B1005","text":"律師"}, {"id":"F2009","text":"架構師"}]}");
        List<JSONObject> list = JSONArray.parseArray(jsonObject.getString("result"), JSONObject.class);

        list.forEach(System.out::println);

        Collections.sort(list, Comparator.comparing(o -> o.getString("id")));

        System.out.println("--------------排序後--------------------");

        list.forEach(System.out::println);
    }

}

三種方法實現字串排序

排序方法概述

對於許多應用，決定順序的鍵都是字串。本篇講述如何利用字串的特殊性質來對其進行高效的排序。

第一類方法會從右到左檢查鍵中的字元。這種方法一般被稱為低位優先（Least-Significant-DigitFirst，LSD）的字串排序。如果將一個字串看做一個256進位制的數位，那麼從右向左檢查字串就等價於先檢查數位的最低位。這種方法最適合用於鍵的長度都相同的字串排序應用。
第二類方法會從左到右檢查鍵中的字元，首先檢視的是最高位的字元。這種方法通常稱為高位優先（MSD）的字串排序。高位優先的字串排序和快速排序類似，因為它們都會將需要排序的陣列切分為獨立的部分並遞迴地用相同的方法處理子陣列來完成排序。它們的區別之處在於高位優先的字串排序演演算法在切分時僅使用鍵的第一個字元，而快速排序的比較則會涉及鍵的全部。
第三種方法是高位優先的字串排序演演算法的改進快速排序，根據鍵的首字母進行三向切分，僅在中間子陣列中的下一個字元（因為鍵的首字母都與切分字元相等）繼續遞迴排序。

鍵索引計數法

作為熱身，我們先學習一種適用於小整數鍵的簡單排序方法。這種叫做鍵索引計數的方法本身就很實用，同時也是要學習的三種排序演演算法中前兩種的基礎。它其實就桶計數。

現在來情景引入，老師在統計學生的分數時可能會遇到以下資料處理問題。學生被分為若干組，標號為1、2、3、4等。在某些情況下，我們希望將全班同學按組分類。因為組的編號是較小的整數，使用鍵索引計數法來排序時很合適的。假設陣列a[]中的每個元素都儲存了一個名字和一個組號，其中組號在0到R-1之間，程式碼a[i].key()會返回指定學生的組號。四個步驟見程式碼

int N = a.length;
int R = 256;    //R為字元基數

String[] aux = new String[N];
int[] count = new int[R + 1];

//計算出現頻率
for (int i = 0; i < N; i++) 
    count[a[i].key() + 1]++;

//將頻率轉換為索引
for (int r = 0; r < R; r++) 
    count[r + 1] += count[r];

//將元素分類
for (int i = 0; i < N; i++) 
    aux[count[a[i].key()]++] = a[i];

//回寫
for (int i = 0; i < N; i++)
    a[i] = aux[i];

命題A：鍵索引計數法排序N個鍵為0到R-1之間的整數的元素需要存取陣列11N+4R+1次

低位優先的字串排序（LSD）

如果字串的長度均為W，那就從右向左以每個位置的字元作為鍵，用鍵索引計數法將字串排序W遍。

命題B：低位優先的字串排序演演算法能夠穩定地將定長字串排序

class LSD{
    // Least-Significant-Digit First
    //低位優先的字串排序(基數排序)
    public static void sort(String[] a, int W) {
        //通過前W個字元將a[]排序
        int N = a.length;
        int R = 256;    //基數
        String[] aux = new String[N];  //輔助陣列

        for(int d = W - 1; d >= 0; d--) {
            //根據第d個字元用鍵索引計數法排序
            int[] count = new int[R + 1];   
            //計算出現頻率
            for (int i = 0; i < N; i++)
                count[a[i].charAt(d) + 1]++;
            //將頻率轉換為索引
            for (int r = 0; r < R; r++)
                count[r + 1] += count[r];
            //將元素分類
            for (int i = 0; i < N; i++) 
                aux[count[a[i].charAt(d)]++] = a[i];
            //回寫
            for (int i = 0; i < N; i++) 
                a[i] = aux[i];
        }
    }
}

在許多字串排序的應用中，鍵的長度可能互不相同。改進後的低位優先的字串排序是可以適應這些情況的。下來講解兩種處理變長鍵排序的演演算法

高位優先的字串排序（MSD）

首先用鍵索引計數法將所有字串按照首字母排序，然後（遞迴地）再將每個首字母所對應的子陣列排序（忽略首字母，因為每一類中的所有首字母都是相同的）。和快速排序一樣，高位優先的字串排序會將陣列切分為能夠獨立排序的子陣列來完成排序任務，但它的切分會為每個首字母得到一個子陣列，而不是像快速排序中那樣產生固定的兩個或者三個切分。

在高位優先的字串排序演演算法中，要特別注意到達字串末尾的情況。在排序中，合理的做法是將所有字元都已被檢查過的字串所在的子陣列排在所有子陣列的前面，這樣就不需要遞迴地將該子陣列排序。為了簡化這兩步計算，我們使用了一個接受兩個引數的私有方法charAt()來將字串中字元索引轉化為陣列索引，當指定的位置超過了字串末尾時該方法返回-1,。然後將所有返回值加1，得到一個非負的int值並用它作為count[]的索引。這種轉換意味著字串中的每個字元都可能產生R+1種不同的值：0表示字串的結尾，1表示字串的第一個字元，2表示字串的第二個字元，等等。因為建索引計數法本來就需要一個額外的位置，所以使用程式碼int count[] = new int[R + 2]

class MSD{
    //高位優先的字串排序
    private static int R = 256;      //基數
    private static final int M = 15; //小陣列的切換閾值
    private static String[] aux;     //陣列分類的輔助陣列
    private static int charAt(String s, int d) {
        if(d < s.length()) {
            return s.charAt(d);
        }else {
            return -1;
        }
    }
    public static void sort(String[] a) {
        int N = a.length;
        aux = new String[N];
        sort(a, 0, N - 1, 0);
    }
    private static void sortInsert(String[] a, int lo, int hi) {
        //小型陣列進行插入排序
        for (int i = lo + 1; i <= hi; i++) {
            for(int j = i; j > lo && a[j].compareTo(a[j - 1]) < 0; j--) {
                String tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
            }
        }
    }
    private static void sort(String[] a, int lo, int hi, int d) {
        //以第d個字元為鍵將a[lo]至a[hi]排序
        if(hi <= lo + M) {
            sortInsert(a, lo, hi);
            return; 
        }
        int [] count = new int[R + 2];    //計算頻率
        for(int i = lo; i <= hi; i++) {
            count[charAt(a[i], d) + 2]++;
        }
        for(int r = 0; r < R + 1; r++) {  //將頻率轉換為索引
            count[r + 1] += count[r];
        }
        for(int i = lo; i <= hi; i++) {   //資料分類
            aux[count[charAt(a[i], d) + 1]++] = a[i];
        }
        for(int i = lo; i <= hi; i++) {   //回寫
            a[i] = aux[i - lo]; 
        }
        //遞迴的以每個字元為鍵進行排序
        for(int r = 0; r <R; r++) {
            sort(a, lo + count[r], lo + count[r + 1] - 1, d + 1);
        }
    }
}

三向字串快速排序

我們也可以根據高位優先的字串排序演演算法改進快速排序，根據鍵的首字母進行三向切分，僅在中間子陣列的下一個字元（因為鍵得出首字母都與切分字母相同）繼續遞迴排序。這個演演算法的實現並不困難，參考往期排序演演算法中的三向切分快排即可。

儘管排序的方式有所不同，但三向字串快速排序根據的仍然是鍵的首字母並使用遞迴的方法將其餘部分排序。對於字串的排序，這個方法比普通的快速排序和高位優先的字串排序更友好。實際上，它就是兩種演演算法的結合。

三向字串快速排序只將陣列切分為三部分，因此當相應的高位優先的字串排序產生的非空切分較多時，它需要移動的資料量就會變大，因此它需要進行一系列的三向切分才能夠取得多向切分的效果。但是，高位優先的字串排序可能會建立大量（空）子陣列，而三向字串快速排序的切分總是隻有三個。因此三向字串快速排序能夠很好地處理等值鍵、有較長公共字首的鍵、取值範圍較小的鍵和小陣列-----所有高位優先的字串排序演演算法不擅長的各種情況。

class Quick3string{
    //三向字串快速排序
    private static int charAt(String s, int d) {
        if(d < s.length()) {
            return s.charAt(d);
        }
        return -1;
    }
    
    public static void sort(String[] a) {
        sort(a, 0, a.length - 1, 0);
    }
    
    private static void sort(String[] a, int lo, int hi, int d) {
        if(hi <= lo) {
            return;
        }
        int lt = lo, gt = hi, i = lo + 1;
        int v = charAt(a[lo], d);
        while(i <= gt) {
            int t = charAt(a[i], d);
            if(t < v) {
                exch(a, lt++, i++);
            }else if(t > v) {
                exch(a, i, gt--);
            }else {
                i++;
            }
        }
        //a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]
        sort(a, lo, lt - 1, d);
        if(v >= 0) {
            sort(a, lt, gt, d + 1);
        }
        sort(a, gt + 1, hi, d);
    }
    
    private static void exch(String[] a, int i, int j) {
        String t = new String(a[i]);
        a[i] = a[j];
        a[j] = t;
    }
}

在將字串陣列a[]排序時，根據它們的首字母進行三向切分，然後（遞迴地）將得到的三個子陣列排序：一個含有所以首字母小於切分字元的字串子陣列，一個含有所以首字母等於切分字串的子陣列（排序時忽略它們的首字母），一個含有所有首字母大於切分字元的字串的子陣列。

以上為個人經驗，希望能給大家一個參考，也希望大家多多支援it145.com。