国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

程序兵法:Java String 源碼的排序算法(一)

CntChen / 3504人閱讀

摘要:從行,可以看出字符串的存儲結構是字符數組。如果不相等,則返回兩字符的編碼值的差值第行當前字符串和另一個字符串,依次字符比較。如果均相等,則返回兩個字符串長度的差值所以要排序,肯定先有比較能力,即實現接口。

摘要: 原創出處 https://www.bysocket.com 「公眾號:泥瓦匠BYSocket 」歡迎關注和轉載,保留摘要,謝謝!

這是泥瓦匠的第103篇原創

《程序兵法:Java String 源碼的排序算法(一)》

文章工程:
* JDK 1.8
* 工程名:algorithm-core-learning # StringComparisonDemo
* 工程地址:https://github.com/JeffLi1993/algorithm-core-learning

一、前言

Q:什么是選擇問題?
選擇問題,是假設一組 N 個數,要確定其中第 K 個最大值者。比如 A 與 B 對象需要哪個更大?又比如:要考慮從一些數組中找出最大項?

解決選擇問題,需要對象有個能力,即比較任意兩個對象,并確定哪個大,哪個小或者相等。找出最大項問題的解決方法,只要依次用對象的比較(Comparable)能力,循環對象列表,一次就能解決。

那么 JDK 源碼如何實現比較(Comparable)能力的呢?

二、java.lang.Comparable 接口

Comparable 接口,從 JDK 1.2 版本就有了,歷史算悠久。Comparable 接口強制了實現類對象列表的排序。其排序稱為自然順序,其 compareTo 方法,稱為自然比較法。

該接口只有一個方法 public int compareTo(T o); ,可以看出

入參 T o :實現該接口類,傳入對應的要被比較的對象

返回值 int:正數、負數和 0 ,代表大于、小于和等于

對象的集合列表(Collection List)或者數組(arrays) ,也有對應的工具類可以方便的使用:

java.util.Collections#sort(List) 列表排序

java.util.Arrays#sort(Object[]) 數組排序

那 String 對象如何被比較的?

三、String 源碼中的算法

String 源碼中可以看到 String JDK 1.0 就有了。那么應該是 JDK 1.2 的時候,String 類實現了 Comparable 接口,并且傳入需要被比較的對象是 String。對象如圖:

String 是一個 final 類,無法從 String 擴展新的類。從 114 行,可以看出字符串的存儲結構是字符(Char)數組。先可以看看一個字符串比較案例,代碼如下:

/**
 * 字符串比較案例
 *
 * Created by bysocket on 19/5/10.
 */
public class StringComparisonDemo {

    public static void main(String[] args) {
        String foo = "ABC";

        // 前面和后面每個字符完全一樣,返回 0
        String bar01 = "ABC";
        System.out.println(foo.compareTo(bar01));

        // 前面每個字符完全一樣,返回:后面就是字符串長度差
        String bar02 = "ABCD";
        String bar03 = "ABCDE";
        System.out.println(foo.compareTo(bar02)); // -1 (前面相等,foo 長度小 1)
        System.out.println(foo.compareTo(bar03)); // -2 (前面相等,foo 長度小 2)

        // 前面每個字符不完全一樣,返回:出現不一樣的字符 ASCII 差
        String bar04 = "ABD";
        String bar05 = "aABCD";
        System.out.println(foo.compareTo(bar04)); // -1  (foo 的 "C" 字符 ASCII 碼值為 67,bar04 的 "D" 字符 ASCII 碼值為 68。返回 67 - 68 = -1)
        System.out.println(foo.compareTo(bar05)); // -32 (foo 的 "A" 字符 ASCII 碼值為 65,bar04 的 "a" 字符 ASCII 碼值為 97。返回 65 - 97 = -32)

        String bysocket01 = "泥瓦匠";
        String bysocket02 = "瓦匠";
        System.out.println(bysocket01.compareTo(bysocket02));// -2049 (泥 和 瓦的 Unicode 差值)
    }
}

運行結果如下:

0
-1
-2
-1
-32
-2049

可以看出, compareTo 方法是按字典順序比較兩個字符串。具體比較規則可以看代碼注釋。比較規則如下:

字符串的每個字符完全一樣,返回 0

字符串前面部分的每個字符完全一樣,返回:后面就是兩個字符串長度差

字符串前面部分的每個字符存在不一樣,返回:出現不一樣的字符 ASCII 碼的差值

中文比較返回對應的 Unicode 編碼值(Unicode 包含 ASCII)

foo 的 ‘C’ 字符 ASCII 碼值為 67

bar04 的 ‘D’ 字符 ASCII 碼值為 68。

foo.compareTo(bar04),返回 67 – 68 = -1

常見字符 ASCII 碼,如圖所示

再看看 String 的 compareTo 方法如何實現字典順序的。源碼如圖:

源碼解析如下:

第 1156 行:獲取當前字符串和另一個字符串,長度較小的長度值 lim

第 1161 行:如果 lim 大于 0 (較小的字符串非空),則開始比較

第 1164 行:當前字符串和另一個字符串,依次字符比較。如果不相等,則返回兩字符的 Unicode 編碼值的差值

第 1169 行:當前字符串和另一個字符串,依次字符比較。如果均相等,則返回兩個字符串長度的差值

所以要排序,肯定先有比較能力,即實現 Comparable 接口。然后實現此接口的對象列表(和數組)可以通過 Collections.sort(和 Arrays.sort)進行排序。

還有 TreeSet 使用樹結構實現(紅黑樹),集合中的元素進行排序。其中排序就是實現 Comparable 此接口

另外,如果沒有實現 Comparable 接口,使用排序時,會拋出 java.lang.ClassCastException 異常。詳細看《Java 集合:三、HashSet,TreeSet 和 LinkedHashSet比較》https://www.bysocket.com/archives/195

四、小結

上面也說到,這種比較其實有一定的弊端:

默認 compareTo 不忽略字符大小寫。如果需要忽略,則重新自定義 compareTo 方法

無法進行二維的比較決策。比如判斷 2 * 1 矩形和 3 * 3 矩形,哪個更大?

比如有些類無法實現該接口。一個 final 類,也無法擴展新的類。其也有解決方案:函數對象(Function Object)

方法參數:定義一個沒有數據只有方法的類,并傳遞該類的實例。一個函數通過將其放在一個對象內部而被傳遞。這種對象通常叫做函數對象(Funtion Object)

在接口方法設計中, T execute(Callback callback) 參數中使用 callback 類似。比如在 Spring 源碼中,可以看出很多設計是:聚合優先于繼承或者實現。這樣可以減少很多繼承或者實現。類似 SpringJdbcTemplate 場景設計,可以考慮到這種 Callback 設計實現。

代碼示例

本文示例讀者可以通過查看下面倉庫的中: StringComparisonDemo 字符串比較案例案例:

Github:github.com/JeffLi1993/…

Gitee:gitee.com/jeff1993/al…

如果您對這些感興趣,歡迎 star、follow、收藏、轉發給予支持!

參考資料

《數據結構與算法分析:Java語言描述(原書第3版)》

https://en.wikipedia.org/wiki/Unicode

https://www.cnblogs.com/vamei/tag/%E7%AE%97%E6%B3%95/

https://www.bysocket.com/archives/2314/algorithm

以下專題教程也許您會有興趣

《程序兵法:算法與數據結構》 https://www.bysocket.com/archives/2314/algorithm

《Spring Boot 2.x 系列教程》
https://www.bysocket.com/springboot

《Java 核心系列教程》
https://www.bysocket.com/archives/2100


(關注微信公眾號,領取 Java 精選干貨學習資料)
(添加我微信:bysocket01。加入純技術交流群,成長技術)


文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/7345.html

相關文章

  • Flink 源碼解析 —— 深度解析 Flink 是如何管理好內存

    摘要:減少垃圾收集壓力因為所有長生命周期的數據都是在的管理內存中以二進制表示的,所以所有數據對象都是短暫的,甚至是可變的,并且可以重用。當然,并不是唯一一個基于且對二進制數據進行操作的數據處理系統。 showImg(https://segmentfault.com/img/remote/1460000020044119?w=1280&h=853); 前言 如今,許多用于分析大型數據集的開源系...

    Edison 評論0 收藏0
  • 金三銀四背后,個 Android 程序面試心得

    摘要:到十二月份,公司開始第二波裁員,我決定主動拿賠償走人。加一個小插曲上面的題是餓了嗎面試問到的。想去的公司沒有面試好,不要氣餒,繼續加油準備。避免打擊自信心。 回顧一下自己這段時間的經歷,九月份的時候,公司通知了裁員,我匆匆忙忙地出去面了幾家,但最終都沒有拿到offer,我感覺今年的寒冬有點冷。到十二月份,公司開始第二波裁員,我決定主動拿賠償走人。后續的面試過程我做了一些準備,基本都能走...

    Achilles 評論0 收藏0
  • 金三銀四,2019大廠Android高級工程師面試題整理

    摘要:原文地址游客前言金三銀四,很多同學心里大概都準備著年后找工作或者跳槽。最近有很多同學都在交流群里求大廠面試題。 最近整理了一波面試題,包括安卓JAVA方面的,目前大廠還是以安卓源碼,算法,以及數據結構為主,有一些中小型公司也會問到混合開發的知識,至于我為什么傾向于混合開發,我的一句話就是走上編程之路,將來你要學不僅僅是這些,豐富自己方能與世接軌,做好全棧的裝備。 原文地址:游客kutd...

    tracymac7 評論0 收藏0

發表評論

0條評論

CntChen

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<