java如何給對象按照字符串屬性進行排序
給對象按照字符串屬性進行排序
在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[]排序時，根據它們的首字母進行三向切分，然後（遞歸地）將得到的三個子數組排序：一個含有所以首字母小於切分字符的字符串子數組，一個含有所以首字母等於切分字符串的子數組（排序時忽略它們的首字母），一個含有所有首字母大於切分字符的字符串的子數組。
以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。