首先先来看一下Arrays.sort()使用的例子。
例子1:
Arrays.sort(int[] a)
//注意一定要用Integer对象类 Integer[] a1 = {34, 57, 46, 89, 98, 12, 55, 84, 29};
Integer[] a2 = {34, 57, 46, 89, 98, 12, 55, 84, 29}; //增序,Arrays.sort()默认升序
Arrays.sort(a1); System.out.println("Arrays.sort()升序:"); for (int i = 0; i <
a1.length; i++) { System.out.print(a1[i] + " "); } //降序,可用Comparator()匿名内部类
Arrays.sort(a2, new Comparator<Integer>() { @Override public int
compare(Integer o1, Integer o2) { return o2.compareTo(o1); } });
System.out.println("\nArrays.sort()降序:"); for (int i = 0; i < a2.length; i++) {
System.out.print(a2[i]+ " "); }
基础知识点:

* 若是基本类型,需要转化为对应的对象类型(如:int转化为Integer)Arrays.sort()可以排序基本对象类型,但是不可以使用基本数据类型。
* Arrays.sort()默认的是升序排序,降序排序可采用Collection.sort()匿名内部类。
* 数组与list一样,需要遍历出来。
运行结果如下:
Arrays.sort()升序: 12 29 34 46 55 57 84 89 98 Arrays.sort()降序: 98 89 84 57 55 46
34 29 12
例子2
Arrays.sort(int[] a, int fromIndex, int toIndex)
//注意一定要用Integer对象类 Integer[] a1 = {34, 57, 46, 89, 98, 12, 55, 84, 29};
//对数组中的第四位到第7位(不包含第七位)(左闭右开原则)进行排序 Arrays.sort(a1,3,6);
System.out.println("Arrays.sort()升序:"); for (int i = 0; i < a1.length; i++) {
System.out.print(a1[i] + " "); }
运行结果如下:

结合文档以及源代码,我们发现,jdk中的Arrays.sort()的实现是通过所谓的双轴快排的算法

双轴快排:

* 快速排序
使用的是分治思想,将原问题分成若干个子问题进行递归解决。选择一个元素作为轴(pivot),通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比轴元素小,另外一部分的所有数据都比轴元素大,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
* 双轴快排(DualPivotQuicksort),顾名思义有两个轴元素pivot1,pivot2,且pivot ≤
pivot2,将序列分成三段:x < pivot1、pivot1 ≤ x ≤ pivot2、x
>pivot2,然后分别对三段进行递归。这个算法通常会比传统的快排效率更高,也因此被作为Arrays.java中给基本类型的数据排序的具体实现。
下面我们以JDK1.8中Arrays对int型数组的排序为例来介绍其中使用的双轴快排:

1.判断数组的长度是否大于286,大于则使用归并排序(merge sort),否则执行2。
// Use Quicksort on small arrays if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true); return; } // Merge sort ......
2.判断数组长度是否小于47,小于则直接采用插入排序(insertion sort),否则执行3。
// Use insertion sort on tiny arrays if (length < INSERTION_SORT_THRESHOLD) {
// Insertion sort ...... }
3.用公式length/8+length/64+1近似计算出数组长度的1/7。
// Inexpensive approximation of length / 7 int seventh = (length >> 3) +
(length >> 6) + 1;
4.取5个根据经验得出的等距点。
/* * Sort five evenly spaced elements around (and including) the * center
element in the range. These elements will be used for * pivot selection as
described below. The choice for spacing * these elements was empirically
determined to work well on * a wide variety of inputs. */ int e3 = (left +
right) >>> 1; // The midpoint int e2 = e3 - seventh; int e1 = e2 - seventh; int
e4 = e3 + seventh; int e5 = e4 + seventh;
5.将这5个元素进行插入排序
// Sort these elements using insertion sort if (a[e2] < a[e1]) { int t =
a[e2]; a[e2] = a[e1]; a[e1] = t; } if (a[e3] < a[e2]) { int t = a[e3]; a[e3] =
a[e2]; a[e2] = t; if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } } if (a[e4] <
a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t; if (t < a[e2]) { a[e3] =
a[e2]; a[e2] = t; if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } } } if (a[e5] <
a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t; if (t < a[e3]) { a[e4] =
a[e3]; a[e3] = t; if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; if (t < a[e1]) {
a[e2] = a[e1]; a[e1] = t; } } } }
6.选取a[e2],a[e4]分别作为pivot1,pivot2。由于步骤5进行了排序,所以必有pivot1
<=pivot2。定义两个指针less和great,less从最左边开始向右遍历,一直找到第一个不小于pivot1的元素,great从右边开始向左遍历,一直找到第一个不大于pivot2的元素。
/* * Use the second and fourth of the five sorted elements as pivots. * These
values are inexpensive approximations of the first and * second terciles of the
array. Note that pivot1 <= pivot2. */ int pivot1 = a[e2]; int pivot2 = a[e4];
/* * The first and the last elements to be sorted are moved to the * locations
formerly occupied by the pivots. When partitioning * is complete, the pivots
are swapped back into their final * positions, and excluded from subsequent
sorting. */ a[e2] = a[left]; a[e4] = a[right]; /* * Skip elements, which are
less or greater than pivot values. */ while (a[++less] < pivot1); while
(a[--great] > pivot2);

7.接着定义指针k从less-1开始向右遍历至great,把小于pivot1的元素移动到less左边,大于pivot2的元素移动到great右边。这里要注意,我们已知great处的元素小于pivot2,但是它于pivot1的大小关系,还需要进行判断,如果比pivot1还小,需要移动到到less左边,否则只需要交换到k处。
/* * Partitioning: * * left part center part right part *
+--------------------------------------------------------------+ * | < pivot1 |
pivot1 <= && <= pivot2 | ? | > pivot2 | *
+--------------------------------------------------------------+ * ^ ^ ^ * | |
| * less k great * * Invariants: * * all in (left, less) < pivot1 * pivot1 <=
all in [less, k) <= pivot2 * all in (great, right) > pivot2 * * Pointer k is
the first index of ?-part. */ outer: for (int k = less - 1; ++k <= great; ) {
int ak = a[k]; if (ak < pivot1) { // Move a[k] to left part a[k] = a[less]; /*
* Here and below we use "a[i] = b; i++;" instead * of "a[i++] = b;" due to
performance issue. */ a[less] = ak; ++less; } else if (ak > pivot2) { // Move
a[k] to right part while (a[great] > pivot2) { if (great-- == k) { break outer;
} } if (a[great] < pivot1) { // a[great] <= pivot2 a[k] = a[less]; a[less] =
a[great]; ++less; } else { // pivot1 <= a[great] <= pivot2 a[k] = a[great]; }
/* * Here and below we use "a[i] = b; i--;" instead * of "a[i--] = b;" due to
performance issue. */ a[great] = ak; --great; } }
8.将less-1处的元素移动到队头,great+1处的元素移动到队尾,并把pivot1和pivot2分别放到less-1和great+1处。
// Swap pivots into their final positions a[left] = a[less - 1]; a[less - 1] =
pivot1; a[right] = a[great + 1]; a[great + 1] = pivot2;
9.至此,less左边的元素都小于pivot1,great右边的元素都大于pivot2,分别对两部分进行同样的递归排序。
// Sort left and right parts recursively, excluding known pivots sort(a, left,
less - 2, leftmost); sort(a, great + 2, right, false);

10.对于中间的部分,如果大于4/7的数组长度,很可能是因为重复元素的存在,所以把less向右移动到第一个不等于pivot1的地方,把great向左移动到第一个不等于pivot2的地方,然后再对less和great之间的部分进行递归排序。
/* * If center part is too large (comprises > 4/7 of the array), * swap
internal pivot values to ends. */ if (less < e1 && e5 < great) { /* * Skip
elements, which are equal to pivot values. */ while (a[less] == pivot1) {
++less; } while (a[great] == pivot2) { --great; } } ...... // Sort center part
recursively sort(a, less, great, false);
另外参考了其他博文,算法思路如下:
算法步骤
1.对于很小的数组(长度小于47),会使用插入排序。
2.选择两个点P1,P2作为轴心,比如我们可以使用第一个元素和最后一个元素。
3.P1必须比P2要小,否则将这两个元素交换,现在将整个数组分为四部分:
(1)第一部分:比P1小的元素。
(2)第二部分:比P1大但是比P2小的元素。
(3)第三部分:比P2大的元素。
(4)第四部分:尚未比较的部分。
在开始比较前,除了轴点,其余元素几乎都在第四部分,直到比较完之后第四部分没有元素。
4.从第四部分选出一个元素a[K],与两个轴心比较,然后放到第一二三部分中的一个。
5.移动L,K,G指向。
6.重复 4 5 步,直到第四部分没有元素。
7.将P1与第一部分的最后一个元素交换。将P2与第三部分的第一个元素交换。
8.递归的将第一二三部分排序。

**总结:**Arrays.sort对升序数组、降序数组和重复数组的排序效率有了很大的提升,这里面有几个重大的优化。
1.对于小数组来说,插入排序效率更高,每次递归到小于47的大小时,用插入排序代替快排,明显提升了性能。
2.双轴快排使用两个pivot,每轮把数组分成3段,在没有明显增加比较次数的情况下巧妙地减少了递归次数。
3.pivot的选择上增加了随机性,却没有带来随机数的开销。
4.对重复数据进行了优化处理,避免了不必要交换和递归。

技术
©2019-2020 Toolsou All rights reserved,
过拟合和欠拟合的形象解释2021 美赛时间安排表Springboot之JPA常用查询方法中国月球车“月兔二号”在月球发现一块奇怪岩石PS制作登录界面C语言程序设计课程设计 之《学生成绩管理系统》消息质量平台系列文章|全链路排查篇年薪20万属于什么水平?答案让人扎心!王者荣耀背景故事整合Jsp+Ajax+Servlet+Mysql实现增删改查(一)