Arrays.sort() 為什麼可以對 int 等數組進行排序?我跟面試官扯了...

2021-01-11 CSDN

作者 | TrueDei

責編 | 王曉曼

出品 | CSDN博客

前言

排序是在程序開發中最常用到的，最常見的就是針對一些數字進行排序。而現實中像商品的名字，訂單的日期等進行排序。Java的JDK中就自帶了Comparable接口，那麼來看下這個，如何與面試官對答如流。

拋下 Arrays.sort() 中排序的算法，一起來揭開這層面紗吧。

1、猜一猜

猜測以下代碼的執行結果是什麼？

int[] ints = {50,1,4,8,3};String [] strings = {"q","a","c"};Arrays.sort(ints);for (String val: strings) { System.out.print(val + " ");}System.out.println();for (int i = 0; i < ints.length; i++) { System.out.print(ints[i]+" ");}

好了，現在猜測結束。

你會很快猜到一下內容：

q a c 134850

你可真是一個小能能，厲害的不要不要的。

但是，如果面試官問你：

為什麼 int 數組， String 數組等等，這些可以使用 Arrays.sort() 進行排序呢？

咱們慢慢揭曉這個答案。

先看幾個原始碼：

1、Integer的原始碼

publicfinalclassIntegerextendsNumberimplementsComparable<Integer> { ..... ..... .....publicintcompareTo(Integer anotherInteger){return compare(this.value, anotherInteger.value); }}

2、Short的原始碼

publicfinalclassShortextendsNumberimplementsComparable<Short> { ..... ..... .....publicintcompareTo(Short anotherShort){return compare(this.value, anotherShort.value); }}

3、String的原始碼

publicfinalclassStringimplementsjava.io.Serializable, Comparable<String>, CharSequence{ ..... ..... .....publicintcompareTo(String anotherString){int len1 = value.length;int len2 = anotherString.value.length;int lim = Math.min(len1, len2);char v1[] = value;char v2[] = anotherString.value;int k = 0;while (k < lim) {char c1 = v1[k];char c2 = v2[k];if (c1 != c2) {return c1 - c2; } k++; }return len1 - len2; }}

發現了什麼？

是不是發現了都實現了Comparable接口和compareTo方法。

對，你現在也許知道怎麼去回答面試官這個問題了，因為他們都實現了Comparable接口和compareTo方法。

3、試試真是如此嗎？不信測試一下

新建二個實體類和一個測試類，一個是Student實體類，一個是User實體類，一個是測試類Test。

Student類

為了方便演示，這裡的Student類實現Comparable接口。

package ComparableInterface;/** * @Auther: truedei * @Date: 2020 /20-5-7 20:29 * @Description: */publicclassStudentimplementsComparable<Student>{privateint age;private String name;publicStudent(){ }publicStudent(int age, String name){this.age = age;this.name = name; }publicintgetAge(){return age; }publicvoidsetAge(int age){this.age = age; }public String getName(){return name; }publicvoidsetName(String name){this.name = name; }@Overridepublic String toString(){return"Student{" +"age=" + age +", name='" + name + '\'' +'}'; }@OverridepublicintcompareTo(Student o){returnthis.getAge() - o.getAge(); }}

User類

為了方便演示，這裡的User類不實現Comparable接口。

package ComparableInterface;/** * @Auther: truedei * @Date: 2020 /20-5-7 20:29 * @Description: */publicclassUser{privateint age;private String name;publicUser(){ }publicUser(int age, String name){this.age = age;this.name = name; }publicintgetAge(){return age; }publicvoidsetAge(int age){this.age = age; }public String getName(){return name; }publicvoidsetName(String name){this.name = name; }@Overridepublic String toString(){return"User{" +"age=" + age +", name='" + name + '\'' +'}'; }}

測試類

package ComparableInterface;import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * @Auther: truedei * @Date: 2020 /20-5-7 20:29 * @Description: */publicclassTest{publicstaticvoidmain(String[] args){ }}

測試1、比較Student類

Student s1 = new Student(19,"張三");Student s2 = new Student(18,"李四");int i = s1.compareTo(s2);if(i>=0){ System.out.println(s1.getName()+"年齡大");}else{ System.out.println(s2.getName()+"年齡大");}

測試結果1：

這個結果也是很容易猜到的，因為Student類實現了Comparable接口，並實現了 compareTo方法。並且是以age做比較的。

張三年齡大

測試2、比較User類

User u1 = new User(12,"王五"); User u2 = new User(22,"趙六");int j = u1.compareTo(u2);if(j>=0){ System.out.println(u1.getName()+"年齡大"); }else{ System.out.println(u2.getName()+"年齡大"); }

測試2的結果：

這個是沒有結果的，因為程序是無法執行的，會報出沒有compareTo這個方法。

原因：

原因很簡單，因為沒有實現Comparable接口。

測試3、對Student類的數組排序

隨便添加進去幾個數據，為了方便理解，我就寫的稍微麻煩了一點。

Student s1 = new Student(19,"張三"); Student s2 = new Student(18,"李四"); Student s3 = new Student(2,"王五"); Student[] students = {s1,s2,s3}; System.out.println("排序前:");for (Student st:students) { System.out.println(st.toString()); } System.out.println();//進行排序 Arrays.sort(students); System.out.println("排序後：");for (Student st:students) { System.out.println(st.toString()); }

測試結果：

是不是有點小驚喜？為什麼可以進行直接排序呢？

沒錯，就是因為實現了那個Comparable接口，而且是根據年齡的大小來排序的。

排序前:Student{age=19, name='張三'}Student{age=18, name='李四'}Student{age=2, name='王五'}排序後：Student{age=2, name='王五'}Student{age=18, name='李四'}Student{age=19, name='張三'}

如果你想從大到小排序怎麼辦？

也很簡單，只需要改變一下compareTo中的方法即可。

修改如下：

@OverridepublicintcompareTo(Student o){// return this.getAge() - o.getAge();return o.getAge()- this.getAge(); }

為了好看，我把三個Student類的數據，修改了一下:

Student s1 = new Student(7,"張三");Student s2 = new Student(18,"李四");Student s3 = new Student(2,"王五");

測試結果:

排序前:Student{age=7, name='張三'}Student{age=18, name='李四'}Student{age=2, name='王五'}排序後：Student{age=18, name='李四'}Student{age=7, name='張三'}Student{age=2, name='王五'}Process finished with exit code 0

測試4、對User類的數組排序

可以先猜測一下，可能排序嗎？

User u1 = new User(12,"王五"); User u2 = new User(22,"趙六"); User u3 = new User(15,"雜七"); User[] users = {u1,u2,u3}; System.out.println("排序前:");for (User user:users) { System.out.println(user.toString()); } System.out.println();//進行排序 Arrays.sort(users); System.out.println("排序後：");for (User user:users) { System.out.println(user.toString()); }

測試結果：

排序前:User{age=12, name='王五'}User{age=22, name='趙六'}User{age=15, name='雜七'}Exception in thread "main" java.lang.ClassCastException: ComparableInterface.User cannot be cast to java.lang.Comparable at java.util.ComparableTimSort.countRunAndMakeAscending(ComparableTimSort.java:320) at java.util.ComparableTimSort.sort(ComparableTimSort.java:188) at java.util.Arrays.sort(Arrays.java:1246) at ComparableInterface.Test.main(Test.java:54)

提示你：

cannot be cast to java.lang.Comparable

說明：無法轉換成Comparable

那麼就得出結論：

沒有實現Comparable接口的類的數組是無法使用Arrays.sort()進行排序的

改造 User類 進一步測試

稍微改造一下：給User類實現Comparable接口。

1、需求如下

因為User類有年齡和姓名，年齡小的優先。

如果年齡相同，那麼比較姓名，按姓名的ascii碼值來排序，例如：a-b-c

2、修改User類

package ComparableInterface;/** * @Auther: truedei * @Date: 2020 /20-5-7 20:29 * @Description: */publicclassUserimplementsComparable<User>{privateint age;private String name;publicUser(){ }publicUser(int age, String name){this.age = age;this.name = name; }publicintgetAge(){return age; }publicvoidsetAge(int age){this.age = age; }public String getName(){return name; }publicvoidsetName(String name){this.name = name; }@Overridepublic String toString(){return"User{" +"age=" + age +", name='" + name + '\'' +'}'; }@OverridepublicintcompareTo(User o){//年齡從小到大if(this.getAge() - o.getAge() > 0){return1; }elseif(this.getAge() - o.getAge() == 0){returnthis.getName().compareTo(o.getName()); }return -1; }}

重點是:

可以看到年齡是從小到大的對比如果this.年齡 - o.年齡 == 0 說明相等，那麼就比較名字@Overridepublic int compareTo(User o) {//年齡從小到大if(this.getAge() - o.getAge() > 0){return1; }elseif(this.getAge() - o.getAge() == 0){returnthis.getName().compareTo(o.getName()); }return-1;}

3、測試

為了方便理解，我把姓名修改成了a,e,s,q,d,g這些字母

為了比較好說明，我找了一個比較簡潔的ascii碼錶：

我們拿a、b、y做為姓名來測試：

System.out.println("a="+(int)'a');System.out.println("b="+(int)'b');System.out.println("y="+(int)'y');

結果：

97<98<121

a<b<y

a=97b=98y=121

正式代碼：

User u1 = new User(12,"b"); User u2 = new User(22,"y"); User u3 = new User(22,"a"); User[] users = {u1,u2,u3}; System.out.println("排序前:");for (User user:users) { System.out.println(user.toString()); } System.out.println();//進行排序 Arrays.sort(users); System.out.println("排序後：");for (User user:users) { System.out.println(user.toString()); }

測試結果：

排序前:User{age=12, name='b'}User{age=22, name='y'}User{age=22, name='a'}排序後：User{age=12, name='b'}User{age=22, name='a'}User{age=22, name='y'}

版權聲明：本文為CSDN博主「TrueDei」的原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處連結及本聲明。

原文連結：

https://truedei.blog.csdn.net/article/details/105981691

相關焦點

  • Sort an Array 數組排序
    ，在平時刷其他題的時候，遇到要排序的時候，一般都會調用系統自帶的排序函數，像 C++ 中直接就調用 sort 函數即可，但是這道題考察的就是排序，再調用系統的排序函數就有些說不過去了。題目給定了每個數字的範圍是 [-50000, 50000]，並不是特別大，這裡可以使用記數排序 Count Sort，在 LeetCode 中也有直接利用這個解法的題Sort Colors，建立一個大小為 100001 的數組 count，然後統計 nums 中每個數字出現的個數，然後再從0遍歷到 100000，對於每個遍歷到的數字i，若個數不為0，則加入 count 數組中對應個數的 i-50000
  • Number of Squareful Arrays 平方數組的個數
    其實這道題有兩個難點，一個是如何求全排列，另一個是如何在生成全排列的過程中驗證平方數組。LeetCode 有好幾道關於全排列的題，比較基本的就是這兩道 Permutations 和 Permutations II，很明顯這道題中的數字是有可能重複的，所以跟後者更接近。其實這道題的解法就是基於 Permutations II 來做的，只不過在過程中加入了判斷平方數組的步驟。
  • java基礎入門-day18-Arrays和Collections類
    本類方法是針對數組的操作！l void sort(type[], int fromIndex, int toIndex) ：這個方法會給指定的數組中從fromIndex下標開始到toIndex下標結束，這一段內容排序！
  • 程式設計師面試通關的 101 道真題
    事先做好練習，不僅可以讓你熟悉題目，而且也可以更自信地向面試官解釋解決方案。編程面試最大的難點之一就在於，編程題目的數量成千上萬，甚至還出現了LeetCode、HackerRank、Codewars、Topcoder、freeCodeCamp、HackerEarth等各大網站來訓練程式設計師如何應對編程面試，對於剛開始找工作的新手來說有點不知所措。
  • 面試官:2,4,6組成最大的數組是多少?回答「642」的被淘汰
    面試官：2，4，6組成最大的數組是多少？這不，我的朋友在面試的時候就遇到了這樣一個奇葩的問。我的朋友小黑是一個剛畢業沒多久的應屆大學生，跟很多大學生一樣，剛畢業的他們打算找一份工作來豐富自己的職場社會經驗，於是便向很多公司投遞了簡歷沒過多久便收到了一家公司的面試邀請，為了能順利的通過面試小黑在面試前做了充足的準備。面試點頭，小黑髮現跟自己一起接受面試的還有兩個求職者，這讓小黑感覺到了不小的壓力。
  • 旋轉數組的最小數字
    原題把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如，數組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個旋轉，該數組的最小值為 1。
  • asp數組隨機排序
    首頁 > 語言 > 關鍵詞 > asp最新資訊 > 正文 asp數組隨機排序
  • 關於快速排序
    對於排序，我就學了冒泡排序，就沒管其他的了，而學霸同學那個時候就學會了，這個也許就是我沒有成為學霸的重要原因。高中三年沒碰計算機競賽，因為那時候自作聰明的我，覺得計算機這種大熱必定會大冷，搞點數學物理這種基礎學科才是要緊的，當然數學物理我也不咋地，哈哈哈。說來也搞笑，大學我雖然是搞ACM和數學建模的，其實快排怎麼排的我也沒去管，要比賽了臨時抱抱佛腳，ACM也就靠簡單題做的快混了3年。
  • python實踐分享:關於排序算法,怎麼選擇sort()或者sorted()?
    各種排序算法以及它們的時間複雜度分析是很多企業面試人員在面試時候經常會問到的問題，這也不難理解，在實際的應用過程中確實會遇到各種需要排序的情況，如按照字母表輸出一個序列、對記錄的多個欄位排序等。還好，Python中的排序相對簡單，常用的函數有 sort()和sorted()兩種。這兩種函數並不完全相同，各有各的用武之地。我們來具體分析一下。
  • LeetCode刷題第三周【數組(簡單)】
    這學期課程主要有圖形學（Computer Graphics）等等的專業課，具體的請看話題列表，每門課我將會開設一個專門的話題。內容會跟隨課程，逐步上傳，包括自學的一些額外筆記。數組是目前Leetcode上題量最多的一個模塊了。刷題前我們來了解一下什麼是數組：數組是在程序設計中，為了處理方便， 把具有相同類型的若干元素按有序的形式組織起來的一種形式。
  • 單片機的C語言中數組的用法
    下面就對數組進行詳細的介紹。（1）一維數組本文引用地址：http://www.eepw.com.cn/article/201611/320327.htm一維數組是最簡單的數組，用來存放類型相同的數據。數據的存放是線性連續的。
  • Python,Numpy,Pandas……數據科學家必備排序技巧
    全文共6168字，預計學習時長12分鐘對數據進行分類整理是數據科學家和數據工程師的基礎工作。Python會提供許多內置庫，優化排序選項。有些庫甚至可以同時在GPU上運行。令人驚奇的是，一些排序方法並沒有使用之前所述的算法類型，其他方法的執行效果也不如預期。選擇使用哪種庫和哪類排序算法著實難辦，因為算法的執行變化很快。
  • 直擊LeetCode最經典二分法算法題:Median of Two Sorted Arrays
    最後決定講一道我個人覺得很有意思的一道題，那就是LeetCode上大名鼎鼎的Median of Two Sorted Arrays。這道題是一道非常經典並且有相當難度的二分查找問題，徹底理解和實現之後其他二分查找問題相信都會迎刃而解。
  • LeetCode數組類知識點&題型總結
    由於數組在存儲時是順序存儲的，存儲數據的內存也是連續的，所以數組在讀取數據時比較容易，隨機訪問速度快，但是插入和刪除就比較費勁了。讀取可以直接根據索引，插入和刪除則比較耗時，插一個數據需要移動大量元素，在內存中空出一個元素的空間，然後將要增加的元素放在其中，如果想刪除一個元素，同樣需要移動大量元素去掉被移動的元素。所以如果需求是快速訪問數據，很少或者幾乎不插入和刪除元素，數組是一個不錯的選擇。
  • 如何使用Numpy數組?
    【連續「Python利用Numpy數組進行數據處理（一）」】2.【聚合函數】數學和統計方法[軸和0]可以通過數組上的一組數學函數對整個數組或某個軸向的數組進行統計計算。In [2]: bools=np.array([False,False,True,False])In [3]: bools.any()Out[3]: TrueIn [4]: bools.all()Out[4]: False4.排序Numpy數組也可以通過sort方法就地排序：In [8]:
  • 怎麼樣更好地理解排序算法
    這個問題糾纏了我好久，總想怎樣才能把各種算法可視化，更容易理解和記憶。排序是一個經典的問題，它以一定的順序對一個數組或列表中的元素進行重新排序。而排序算法也是各有千秋，每個都有自身的優點和局限性。雖然這些算法平常根本就不用自己去編寫，但作為一個有追求的程式設計師，還是要了解它們從不同角度解決排序問題的思想。
  • 面試題解| Median of two Sorted Arrays
    面試官會這麼輕易就放過你嗎？顯然是不可能滴~~小編偷看了一下題目描述下的「challenge」標籤，原來這道題的最優解是 O(log(m + n)) 的複雜度。(m + n) 是倆數組合併後的總長度  L，看到 O(log L) 這樣的複雜度，而且還是有序數組，能想到哪個算法嗎？沒錯，就是二分查找！
  • 靈魂拷問:如何檢查 Java 數組中是否包含某個值?
    我曾在某個技術論壇上分享過一篇非常基礎的文章，結果遭到了無數的嘲諷：「這麼水的文章不值得分享。」我點開他的頭像進入他的主頁，發現他從來沒有分享過一篇文章，不過倒是在別人的博客下面留下過不少的足跡，大多數都是冷嘲熱諷。我就納悶了，技術人不都應該像我這樣低調謙遜嗎？怎麼戾氣這麼重！好了，讓我們來步入正題。如何檢查數組（未排序）中是否包含某個值 ？