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

2020-12-15 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

相關焦點

  • 10大經典排序算法,20+張圖就搞定
    temp=j; } } swap(a[i],a[temp]); //交換函數 }} 相比冒泡排序的不斷交換，簡單選擇排序是等到合適的關鍵字出現後再進行交換，並且交換一次就可以達到一次冒泡的效果。圖示過程可以看見，相比直接插入排序由於可以每趟進行分段操作，故整體效率體現較高。
  • 揭開「拓撲排序」的神秘面紗
    作者 | 小齊本齊責編 | Carol來源 | 碼農田小齊Topological sort 又稱 Topological order，這個名字有點迷惑性，因為拓撲排序並不是一個純粹的排序算法，它只是針對某一類圖，找到一個可以執行的線性順序
  • 基礎不牢地動山搖記住 Java 面試中常用的八種排序算法與代碼實現
    代碼實現如下：public void insertSort(int[] a){int length=a.length;//數組長度，將這個提取出來是為了提高速度。速度僅次於快排，內存少的時候使用，可以進行並行計算的時候使用。
  • 看動畫學算法之:排序-冒泡排序
    簡介排序可能是所有的算法中最最基礎和最最常用的了。排序是一個非常經典的問題，它以一定的順序對一個數組（或一個列表）中的項進行重新排序。排序算法有很多種，每個都有其自身的優點和局限性。今天我們來學習最最簡單的冒泡排序算法。
  • 10道虐心的Java面試題,被面試官虐哭了,同事一題都沒答對
    有一天，小王告訴我，他去一家公司面試 Java 崗，結果被面試官虐哭了。整整 10 道 Java 面試題，小王一道也沒答正確。　　他沮喪地給我說，「哥，說點我的情況，你願意聽嗎？我和一個女孩相處，女孩大我兩歲，我非科班。本來打算國慶換一家薪水高點的，好確認關係。
  • 怎麼樣更好地理解排序算法
    這個問題糾纏了我好久，總想怎樣才能把各種算法可視化，更容易理解和記憶。排序是一個經典的問題，它以一定的順序對一個數組或列表中的元素進行重新排序。而排序算法也是各有千秋，每個都有自身的優點和局限性。>增量遞減排序，是對直接插入算法的改進，基於以下兩點性質：插入排序在對幾乎已排好序的數據操作時，效率高，可以達到線性排序的效率但插入排序一般來說是低效的，因為插入排序每次只能移動一位數據
  • 手敲一遍數據結構和排序算法
    ，這裡的臨時數組是存排序後的元素，排完後再複製到原數組中inttempIndex=left;// 循環比較，直至左邊組或右邊組沒有剩餘元素了才停止while (l<=mid&&r<=right) {// 可以想像最簡單的情況，倒數第二層，有兩個元素，需要對這兩個元素排序
  • 堆排序算法
    堆排序的基本思想是：將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。將其與末尾元素進行交換，此時末尾就為最大值。然後將剩餘n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。
  • Python中的快速排序算法,快速排序的優缺點,中級python技術點
    Python中的快速排序算法就像合併排序一樣，快速排序算法採用分治法的原理將輸入數組分為兩個列表，第一個包含小項目，第二個包含大項目。然後，該算法將對兩個列表進行遞歸排序，直到對結果列表進行完全排序為止。劃分輸入列表稱為對列表進行分區。
  • 為什麼數組下標從0開始
    在討論數組下標為什麼從0開始之前我們先回顧一下數組有什麼特點。數組的優點：1.內存中佔據連續的內存空間2.數據隨機訪問，也就是說獲取數據非常高效那為什麼說數組的數據可以隨機訪問而且取數據非常高效呢？下面我們來看這樣一張圖：上圖是一個長度為10的整型數組，我們假設數組的首地址是1000。不難看出當下標從0開始的時候，數組中各個元素的首地址計算公式是：a[i]地址 = 1000 + i*4。（其中1000是數組a的首地址，4是每個元素佔的內存大小（int佔4個字節大小）。）
  • 5分鐘弄懂的五大常用算法之「分治法」,以C語言歸併排序算法為例
    在處理數組排序時，如果數組中只有 1 個元素，那麼該數組本身就可看作是排好序的數組。如果數組中有 2 個元素，那麼最多只需比較一次就可以得到排好序的數組。這其實是歸併排序法的核心，也即規模越小的數組，對其排序越簡單。下圖是一個長度為 5 的數組，為了排序，先把它拆分到不能繼續拆為止。
  • 搞定HashMap面試,深入講解HashMap的工作原理
    為什麼HashMap深受面試官青睞，我想有這3個原因：常用、基礎線程不安全，容易出問題大廠都在問，自己不問顯得面試官沒水平Hash虐我千百遍，我視它為初戀，真的是又愛又恨。但是40億的數組內存是放不下的，只能進行壓縮。最簡單的方法就是取模，hash%table.length就能計算出index。我們能想到，大師也想到了。只是大師想的更周全。
  • JavaScript面經之冒泡排序
    文/大白老師圖/大白老師我們去大廠面試前端的時候，最容易被問及的一個內容就是排序，而其中，冒泡排序作為最基礎的排序算法，很多時候是被要求進行手寫代碼的，面試官通過對手寫代碼的考察，可以看出求職者的算法基礎功底
  • 看完這篇 HashMap,和面試官扯皮就沒問題了
    int 佔用四個字節，按說最大容量應該是左移 31 位，為什麼 HashMap 最大容量是左移 30 位呢？因為在數值計算中，最高位也就是最左位的位 是代表著符號為，0 -> 正數，1 -> 負數，容量不可能是負數，所以 HashMap 最高位只能移位到 2 ^ 30 次冪。
  • 面試常問的數據結構十大經典算法
    它的基本思想是：在數據序列中選擇一個元素作為基準值，每次從數據序列的兩端開始交替進行，將小於基準值元素交換到序列前端，將大於基準值的元素交換到序列後端，介於兩者之間的位置則成為基準值的最終位置。同時，序列被劃分成兩個子序列，再分別對兩個子序列進行快速排序，直到子序列長度為1，則完成排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
  • 調整數組順序使奇數位於偶數前面(劍指 Offer 題解,面試)
    調整數組順序使奇數位於偶數前面題目描述需要保證奇數和奇數，偶數和偶數之間的相對位置不變，這和書本不太一樣。解題思路方法一：創建一個新數組，時間複雜度 O(N)，空間複雜度 O(N)。package 劍指offer.調整數組順序使奇數位於偶數前面_21;/*作者 :XiangLin文件 :OrderArray.javaIDE :IntelliJ IDEA*/
  • 面試再問HashMap,求你把這篇文章發給他!
    除此之外還可以引出線程安全的問題，HashMap是我在初學階段學到的設計的最為巧妙的集合，裡面有很多細節以及優化技巧都值得我們深入學習，話不多說先看看相關的面試題： 默認大小、負載因子以及擴容倍數是多少 底層數據結構 如何處理 hash