快捷導(dǎo)航

java如何給對(duì)象按照字符串屬性進(jìn)行排序

更新時(shí)間：2022年11月15日 17:14:52 作者：野生java研究僧

這篇文章主要介紹了java如何給對(duì)象按照字符串屬性進(jìn)行排序，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

給對(duì)象按照字符串屬性進(jìn)行排序

在java中對(duì)象進(jìn)行排序，排序的屬性是string，我們只需要實(shí)現(xiàn)Comparator接口，然后實(shí)現(xiàn)比較的方式。

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\":\"設(shè)計(jì)師\"}, {\"id\":\"G1009\",\"text\":\"自由職業(yè)\"}, {\"id\":\"E2007\",\"text\":\"學(xué)生\"}, {\"id\":\"C1009\",\"text\":\"教師\"}, {\"id\":\"A1002\",\"text\":\"醫(yī)生\"}, {\"id\":\"B1005\",\"text\":\"律師\"}, {\"id\":\"F2009\",\"text\":\"架構(gòu)師\"}]}");
        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\":\"設(shè)計(jì)師\"}, {\"id\":\"G1009\",\"text\":\"自由職業(yè)\"}, {\"id\":\"E2007\",\"text\":\"學(xué)生\"}, {\"id\":\"C1009\",\"text\":\"教師\"}, {\"id\":\"A1002\",\"text\":\"醫(yī)生\"}, {\"id\":\"B1005\",\"text\":\"律師\"}, {\"id\":\"F2009\",\"text\":\"架構(gòu)師\"}]}");
        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\":\"設(shè)計(jì)師\"}, {\"id\":\"G1009\",\"text\":\"自由職業(yè)\"}, {\"id\":\"E2007\",\"text\":\"學(xué)生\"}, {\"id\":\"C1009\",\"text\":\"教師\"}, {\"id\":\"A1002\",\"text\":\"醫(yī)生\"}, {\"id\":\"B1005\",\"text\":\"律師\"}, {\"id\":\"F2009\",\"text\":\"架構(gòu)師\"}]}");
        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);
    }

}

三種方法實(shí)現(xiàn)字符串排序

排序方法概述

對(duì)于許多應(yīng)用，決定順序的鍵都是字符串。本篇講述如何利用字符串的特殊性質(zhì)來對(duì)其進(jìn)行高效的排序。

第一類方法會(huì)從右到左檢查鍵中的字符。這種方法一般被稱為低位優(yōu)先（Least-Significant-DigitFirst，LSD）的字符串排序。如果將一個(gè)字符串看做一個(gè)256進(jìn)制的數(shù)字，那么從右向左檢查字符串就等價(jià)于先檢查數(shù)字的最低位。這種方法最適合用于鍵的長度都相同的字符串排序應(yīng)用。
第二類方法會(huì)從左到右檢查鍵中的字符，首先查看的是最高位的字符。這種方法通常稱為高位優(yōu)先（MSD）的字符串排序。高位優(yōu)先的字符串排序和快速排序類似，因?yàn)樗鼈兌紩?huì)將需要排序的數(shù)組切分為獨(dú)立的部分并遞歸地用相同的方法處理子數(shù)組來完成排序。它們的區(qū)別之處在于高位優(yōu)先的字符串排序算法在切分時(shí)僅使用鍵的第一個(gè)字符，而快速排序的比較則會(huì)涉及鍵的全部。
第三種方法是高位優(yōu)先的字符串排序算法的改進(jìn)快速排序，根據(jù)鍵的首字母進(jìn)行三向切分，僅在中間子數(shù)組中的下一個(gè)字符（因?yàn)殒I的首字母都與切分字符相等）繼續(xù)遞歸排序。

鍵索引計(jì)數(shù)法

作為熱身，我們先學(xué)習(xí)一種適用于小整數(shù)鍵的簡單排序方法。這種叫做鍵索引計(jì)數(shù)的方法本身就很實(shí)用，同時(shí)也是要學(xué)習(xí)的三種排序算法中前兩種的基礎(chǔ)。它其實(shí)就桶計(jì)數(shù)。

現(xiàn)在來情景引入，老師在統(tǒng)計(jì)學(xué)生的分?jǐn)?shù)時(shí)可能會(huì)遇到以下數(shù)據(jù)處理問題。學(xué)生被分為若干組，標(biāo)號(hào)為1、2、3、4等。在某些情況下，我們希望將全班同學(xué)按組分類。因?yàn)榻M的編號(hào)是較小的整數(shù)，使用鍵索引計(jì)數(shù)法來排序時(shí)很合適的。假設(shè)數(shù)組a[]中的每個(gè)元素都保存了一個(gè)名字和一個(gè)組號(hào)，其中組號(hào)在0到R-1之間，代碼a[i].key()會(huì)返回指定學(xué)生的組號(hào)。四個(gè)步驟見代碼

int N = a.length;
int R = 256; ? ?//R為字符基數(shù)

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

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

//將頻率轉(zhuǎn)換為索引
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：鍵索引計(jì)數(shù)法排序N個(gè)鍵為0到R-1之間的整數(shù)的元素需要訪問數(shù)組11N+4R+1次

低位優(yōu)先的字符串排序（LSD）

如果字符串的長度均為W，那就從右向左以每個(gè)位置的字符作為鍵，用鍵索引計(jì)數(shù)法將字符串排序W遍。

命題B：低位優(yōu)先的字符串排序算法能夠穩(wěn)定地將定長字符串排序

class LSD{
?? ?// Least-Significant-Digit First
?? ?//低位優(yōu)先的字符串排序(基數(shù)排序)
?? ?public static void sort(String[] a, int W) {
?? ??? ?//通過前W個(gè)字符將a[]排序
?? ??? ?int N = a.length;
?? ??? ?int R = 256; ? ?//基數(shù)
?? ??? ?String[] aux = new String[N]; ?//輔助數(shù)組\

?? ??? ?for(int d = W - 1; d >= 0; d--) {
?? ??? ??? ?//根據(jù)第d個(gè)字符用鍵索引計(jì)數(shù)法排序
?? ??? ??? ?int[] count = new int[R + 1]; ??
?? ??? ??? ?//計(jì)算出現(xiàn)頻率
?? ??? ??? ?for (int i = 0; i < N; i++)
?? ??? ??? ??? ?count[a[i].charAt(d) + 1]++;
?? ??? ??? ?//將頻率轉(zhuǎn)換為索引
?? ??? ??? ?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];
?? ??? ?}
?? ?}
}

在許多字符串排序的應(yīng)用中，鍵的長度可能互不相同。改進(jìn)后的低位優(yōu)先的字符串排序是可以適應(yīng)這些情況的。下來講解兩種處理變長鍵排序的算法

高位優(yōu)先的字符串排序（MSD）

首先用鍵索引計(jì)數(shù)法將所有字符串按照首字母排序，然后（遞歸地）再將每個(gè)首字母所對(duì)應(yīng)的子數(shù)組排序（忽略首字母，因?yàn)槊恳活愔械乃惺鬃帜付际窍嗤模?。和快速排序一樣，高位?yōu)先的字符串排序會(huì)將數(shù)組切分為能夠獨(dú)立排序的子數(shù)組來完成排序任務(wù)，但它的切分會(huì)為每個(gè)首字母得到一個(gè)子數(shù)組，而不是像快速排序中那樣產(chǎn)生固定的兩個(gè)或者三個(gè)切分。

在高位優(yōu)先的字符串排序算法中，要特別注意到達(dá)字符串末尾的情況。在排序中，合理的做法是將所有字符都已被檢查過的字符串所在的子數(shù)組排在所有子數(shù)組的前面，這樣就不需要遞歸地將該子數(shù)組排序。為了簡化這兩步計(jì)算，我們使用了一個(gè)接受兩個(gè)參數(shù)的私有方法charAt()來將字符串中字符索引轉(zhuǎn)化為數(shù)組索引，當(dāng)指定的位置超過了字符串末尾時(shí)該方法返回-1,。然后將所有返回值加1，得到一個(gè)非負(fù)的int值并用它作為count[]的索引。這種轉(zhuǎn)換意味著字符串中的每個(gè)字符都可能產(chǎn)生R+1種不同的值：0表示字符串的結(jié)尾，1表示字符串的第一個(gè)字符，2表示字符串的第二個(gè)字符，等等。因?yàn)榻ㄋ饕?jì)數(shù)法本來就需要一個(gè)額外的位置，所以使用代碼int count[] = new int[R + 2]

class MSD{
?? ?//高位優(yōu)先的字符串排序
?? ?private static int R = 256; ? ? ?//基數(shù)
?? ?private static final int M = 15; //小數(shù)組的切換閾值
?? ?private static String[] aux; ? ? //數(shù)組分類的輔助數(shù)組
?? ?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) {
?? ??? ?//小型數(shù)組進(jìn)行插入排序
?? ??? ?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個(gè)字符為鍵將a[lo]至a[hi]排序
?? ??? ?if(hi <= lo + M) {
?? ??? ??? ?sortInsert(a, lo, hi);
?? ??? ??? ?return;?
?? ??? ?}
?? ??? ?int [] count = new int[R + 2]; ? ?//計(jì)算頻率
?? ??? ?for(int i = lo; i <= hi; i++) {
?? ??? ??? ?count[charAt(a[i], d) + 2]++;
?? ??? ?}
?? ??? ?for(int r = 0; r < R + 1; r++) { ?//將頻率轉(zhuǎn)換為索引
?? ??? ??? ?count[r + 1] += count[r];
?? ??? ?}
?? ??? ?for(int i = lo; i <= hi; i++) { ? //數(shù)據(jù)分類
?? ??? ??? ?aux[count[charAt(a[i], d) + 1]++] = a[i];
?? ??? ?}
?? ??? ?for(int i = lo; i <= hi; i++) { ? //回寫
?? ??? ??? ?a[i] = aux[i - lo];?
?? ??? ?}
?? ??? ?//遞歸的以每個(gè)字符為鍵進(jìn)行排序
?? ??? ?for(int r = 0; r <R; r++) {
?? ??? ??? ?sort(a, lo + count[r], lo + count[r + 1] - 1, d + 1);
?? ??? ?}
?? ?}
}

三向字符串快速排序

我們也可以根據(jù)高位優(yōu)先的字符串排序算法改進(jìn)快速排序，根據(jù)鍵的首字母進(jìn)行三向切分，僅在中間子數(shù)組的下一個(gè)字符（因?yàn)殒I得出首字母都與切分字母相同）繼續(xù)遞歸排序。這個(gè)算法的實(shí)現(xiàn)并不困難，參考往期排序算法中的三向切分快排即可。

盡管排序的方式有所不同，但三向字符串快速排序根據(jù)的仍然是鍵的首字母并使用遞歸的方法將其余部分排序。對(duì)于字符串的排序，這個(gè)方法比普通的快速排序和高位優(yōu)先的字符串排序更友好。實(shí)際上，它就是兩種算法的結(jié)合。

三向字符串快速排序只將數(shù)組切分為三部分，因此當(dāng)相應(yīng)的高位優(yōu)先的字符串排序產(chǎn)生的非空切分較多時(shí)，它需要移動(dòng)的數(shù)據(jù)量就會(huì)變大，因此它需要進(jìn)行一系列的三向切分才能夠取得多向切分的效果。但是，高位優(yōu)先的字符串排序可能會(huì)創(chuàng)建大量（空）子數(shù)組，而三向字符串快速排序的切分總是只有三個(gè)。因此三向字符串快速排序能夠很好地處理等值鍵、有較長公共前綴的鍵、取值范圍較小的鍵和小數(shù)組-----所有高位優(yōu)先的字符串排序算法不擅長的各種情況。

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;
?? ?}
}

在將字符串?dāng)?shù)組a[]排序時(shí)，根據(jù)它們的首字母進(jìn)行三向切分，然后（遞歸地）將得到的三個(gè)子數(shù)組排序：一個(gè)含有所以首字母小于切分字符的字符串子數(shù)組，一個(gè)含有所以首字母等于切分字符串的子數(shù)組（排序時(shí)忽略它們的首字母），一個(gè)含有所有首字母大于切分字符的字符串的子數(shù)組。

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: