JDK中的排序：Arrays.sort的源码实现

梦里梦外; 2023-10-06 21:12 48阅读 0赞

## JDK中的排序：Arrays.sort的源码实现 ##

#### 文章目录 ####

*  JDK中的排序：Arrays.sort的源码实现
 *   *   *  Java中的排序并没有那么简单
         *  整体看看Arrays.sort的所有重载方法
         *  对基本数据类型数组的排序
         *  对Object数组和泛型数组的排序
         *  在使用Arrays.sort时需要注意的点

#### Java中的排序并没有那么简单 ####

JDK中的排序是如何实现的？用了什么算法？或许有人说用了快排，但事实上JDK中排序的实现并没有那么简单，我们进入Arrays.sort的源码来一探究竟

#### 整体看看Arrays.sort的所有重载方法 ####

Arrays.sort作为重载方法，具有很多不同的参数实现：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]  
  从排序是对数组整体排序还是部分排序来看，可分为两类，部分排序即需要传入排序部分的起终点，根据我们的经验，整体排序可能是调用的部分排序的sort方法，不过传入的起点为0，终点为length - 1，看看源码：  
![在这里插入图片描述][857dfaac643c4969bac7e9d52a1cef58.png]  
![在这里插入图片描述][c737af96f5de4664a762a2b6637d6214.png]  
  我们发现整体排序并不是调用的部分排序的方法，`Arrays.sort(int[] a)`和`Arrays.sort(int[] a, int fromIndex, int toIndex)`只是个入口，它们都会去调用`DualPivotQuicksort.sort`方法，都会传入排序部分的起终点，不过整体排序传入的起终点为0和length - 1。  
  从数组元素的类型来看，可以将Arrays.sort分为对基本数据类型的排序和对泛型及Object数组的排序。进入源码我们可以发现：对于基本数据类型数组的排序，Arrays.sort都将调用`DualPivotQuicksort.sort`方法，而泛型及Object数组的排序实现则与之不同。

#### 对基本数据类型数组的排序 ####

对于基本数据类型数组的排序，Arrays.sort都将调用`DualPivotQuicksort.sort`方法，我们来看看这个方法的部分源码：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 3]

在该方法的最开始，会进行判断，若数组长度<286，将调用`sort(a, left, right, true)`，我们来看看该方法：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
  也就是说，若数组长度较小，长度<47，将使用插入排序。若数组长度>=47，将使用快速排序。这是由排序算法的特性决定的，因为在数组长度很小时，在大量测试的平均结果下，插入排序将快于快排。  
  那么当数组长度>=286时呢？我们重新回到`DualPivotQuicksort.sort`方法，发现它会对数组的结构性进行判断，若数组基本有序，则将使用归并排序，若数组的元素排列较为混乱，则调用`sort(a, left, right, true)`方法，由于数组长度>=286，也>=47，因此会进行快速排序。为什么这样设计也是由排序算法的特性决定的，虽然快排和归并排序的（平均）时间复杂度是一样的，但对于基本有序的数组，归并排序的速度会比快速排序快，而对于近乎无序的数组，归并排序速度会比快速排序慢。  
  总结一下，对于基本数据类型数组的排序，排序算法的选择和数组长度的关系如下：

<table> 
 <thead> 
  <tr> 
   <th>数组长度</th> 
   <th>所使用的排序算法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>length &lt; 47</td> 
   <td>插入排序</td> 
  </tr> 
  <tr> 
   <td>47 &lt;= length &lt; 286</td> 
   <td>快速排序</td> 
  </tr> 
  <tr> 
   <td>length &gt;= 286 且数组基本有序</td> 
   <td>归并排序</td> 
  </tr> 
  <tr> 
   <td>length &gt;= 286 且数组基本无序</td> 
   <td>快速排序</td> 
  </tr> 
 </tbody> 
</table>

#### 对Object数组和泛型数组的排序 ####

对于泛型数组的排序，我们可以传入实现了Comparator接口的类的对象，也可以不传，实际上传和不传都是调用的同一个方法，只不过不传入时，对应的参数为null。我们来看看Arrays.sort对Object数组和泛型数组的排序源码：  
![在这里插入图片描述][92d5c97dec4d4f6c99a7465116e39ee7.png]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
  我们发现有个if else条件判断最终要调用哪个方法，而JDK8会默认选择TimSort作为排序算法。TimSort算法是一种起源于归并排序和插入排序的混合排序算法，原则上TimSort是归并排序，但小片段的合并中用了插入排序。对于泛型数组的排序，若不传入实现了Comparator接口的类的对象，将调用`sort(Object[] a)`方法  
  对于上述两个Arrays.sort的重载方法，它们都只是入口，而它们最终调用的排序方法不同，一个是`ComparableTimSort.sort`，一个是`TimSort.sort`。我们进入源码来看看两者的区别：

首先来看看对Object数组排序将调用的`ComparableTimSort.sort`方法的部分源码：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 7]

`ComparableTimSort.sort`将会调用`countRunAndMakeAscending`方法和`binarySort`方法，而这两个方法都有将数组元素强转为Comparable接口类型的操作，因为它需要调用Comparable接口中的compareTo方法进行元素间的比较，Comparable接口中只定义了一个方法，那就是compareTo。

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 8]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 9]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 10]  
  因此，若调用Arrays.sort(Object\[\] o)对Object数组进行排序，但数组元素类型表示的类并没有实现Comparable接口，那么Java将认为该类的对象是无法比较的，一定会抛出ClassCastException异常，比如：  
![在这里插入图片描述][4e8c8882ba7548fb8bd6ccc0da54299b.png]

我们再来看看对泛型数组排序将调用的`TimSort.sort`方法：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 11]  
  我们发现它也会去调用`countRunAndMakeAscending`方法和`binarySort`方法，但这两个方法是泛型版的，这是JDK的老套路了，当年为了支持泛型，复刻了很多原有方法的泛型版本，我们来看看源码：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 12]  
  我们发现在泛型版本中，它会使用我们传入的参数c，即实现了Comparator接口的类的对象的compare方法进行元素之间的比较，Comparator接口定义了包括compare方法在内的很多方法。  
  因此，若对泛型数组进行排序，要么数组元素表示的类实现了Comparable接口（调用Arrays.sort(T\[\] a）相当于调用Arrays.sort(Object\[\] a))，要么调用Arrays.sort时传入实现了Comparator接口的类的对象，否则一定会抛异常。

有人可能会问，那对于包装类的数组呢，比如Integer类型的数组，我都是直接去排序的，为什么没抛异常？那是因为包装类都实现了Comparable接口，都是可比较的

#### 在使用Arrays.sort时需要注意的点 ####

JDK中的Arrays.sort实际上采用的是设计模式中的模板模式，它将排序算法的步骤封装了起来，而将如何比较两个数组元素交给了程序员来实现。当我们排序自定义类时，我们可以让这个类实现Comparable接口，并重写其compareTo方法。也可以创建一个实现了Comparator接口的类，重写其compare方法。具体如何比较两个数组元素的逻辑就写在了需要重写的这两个方法中。  
  比较两个数组元素o1与o2的大小无非三种结果：o1>o2，o1=o2，o1<o2。因此compareTo方法和compare方法的返回值有三种情况，这是针对默认升序设计的，当o1>o2，返回一个正整数，若o1=o2，返回0，若o1<o2，返回一个负整数。对于实现了Comparable接口的类，o1即为this，表示当前类对象。若我们在重写方法的逻辑中按上述对应关系去返回对应值，则调用Arrays.sort将会得到升序结果，若把对应关系写反，则会得到降序结果。  
  需要注意的是，compareTo方法和compare方法的返回值一定要具有一个负整数和一个正整数，否则TimSort将失效，我们还是不能偷懒，得规规矩矩把正负零三种返回值给写上。

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/64e8e46a74f54fec9a0d1bad6cb45fb7.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[857dfaac643c4969bac7e9d52a1cef58.png]: https://img-blog.csdnimg.cn/857dfaac643c4969bac7e9d52a1cef58.png
[c737af96f5de4664a762a2b6637d6214.png]: https://img-blog.csdnimg.cn/c737af96f5de4664a762a2b6637d6214.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/58e52113d72d465e98331cd9b91fdea9.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/c3a0d2d2885647efad8ee9434294f295.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/13ffd0bc8eab4fd99f5a2c8dfb97b354.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/2261afc250e04a5ba94638d5d3ab879f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 5]: https://img-blog.csdnimg.cn/036dd1c7e6b34bf285799fa6bce2e65f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[92d5c97dec4d4f6c99a7465116e39ee7.png]: https://img-blog.csdnimg.cn/92d5c97dec4d4f6c99a7465116e39ee7.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 6]: https://img-blog.csdnimg.cn/07356a8629444676a871c96f86306efa.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 7]: https://img-blog.csdnimg.cn/ffabc3e3e7e1441280017e8d08fea410.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 8]: https://img-blog.csdnimg.cn/df55f1f2bbea49e0bfe38165c6c597b7.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 9]: https://img-blog.csdnimg.cn/03ed2d8cad9c477ba99e95b34733ab5a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 10]: https://img-blog.csdnimg.cn/8717587be2e44e0baf17405b45c8acc0.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[4e8c8882ba7548fb8bd6ccc0da54299b.png]: https://img-blog.csdnimg.cn/4e8c8882ba7548fb8bd6ccc0da54299b.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 11]: https://img-blog.csdnimg.cn/e556a79983074ff8a07b95fef709497f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 12]: https://img-blog.csdnimg.cn/079dc000465b452fa1dd6b12a2daa176.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16