Java使用Arrays.sort()方法实现给对象排序

Java使用Arrays.sort()方法实现给对象排序

目录使用Arrays.sort()方法给对象排序麻烦的方法Arrays.sort()方法浅谈Arrays.sort()原理例子1基础知识点例子2双轴快排另外参考了其他博文，算法思路如下

使用Arrays.sort()方法给对象排序

当我们给一个整型数组或者浮点型http://之类的数组排序的时候，很简单就可以达到我们排序的目的，无非是排序算法的问题。那么，如果我们现在想根据对象的一个属性值给一个对象数组进行排序呢？

假如我们现在有一个Car类型，Car类中有一个double型的speed属性用来描述车辆的速度，现在我们想根据车速来对一个Car数组中的车辆进行排序，怎么做呢？

public class Car{

private double speed;//车辆的速度属性

public Car(double speed) {

this.speed = speed;

}

public double getSpeed() {

return speed;

}

public void setSpeed(double speed) {

this.speed = speed;

}

}

麻烦的方法

我们可以通过比较对象的属性值，根据比较结果，对对象数组进行排序，例如，假如我们使用的是冒泡排序的话，就需要写成下面这样：

for(int i=0;i

{

for(int j=0;j

{

if(a[j].getSpeed()>a[j+1].getSpeed())//交换操作

{

Car temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

}

}

}

这样写确实能实现了效果，但是未必性能很好，由于是自己写的，写起来也会比较麻烦，下面的方法会更好

Arrays.sort()方法

我们先来看看用Array.sort()方法实现对车辆排序的代码：

其中，Car这个类有两种写法：

第一种写法：

public class Car implements Comparable{

private double speed;

public Car(double speed) {

this.speed = speed;

}

public double getSpeed() {

return speed;

}

public void setSpeed(double speed) {

this.speed = speed;

}

@Override

public int compareTo(Car newCar) {

return Double.compare(this.getSpeed(),newCar.getSpeed());

}

}

第二种写法

public class Car implements Comparable{

private double speed;

public Car(double speed) {

this.speed = speed;

}

public double getSpeed() {

return speed;

}

public void setSpeed(double speed) {

this.speed = speed;

}

@Override

public int compareTo(Object newCar) {

return Double.compare(this.getSpeed(),((Car)newCar).getSpeed());

}

}

main方法：

public class Test8 {

public static void main(String[] args) {

Car[] carList = new Car[3];

carList[0] = new Car(30);

carList[1] = new Car(10);

carList[2] = new Car(55);

Arrays.sort(carList);

for(Car c:carList)

{

System.out.println(c.getSpeed());

}

}

}

输出结果：

解析：

顾名思义，Arrays类的sort()方法是对一个数组进行排序的方法，sort()方法的参数是一个对象数组，也就是要排序的那个数组，但是有些特别的是，这个对象数组中存储的对象的类必须实现了Comparable接口。

Comparable接口是用来比较大小的，要实现这个接口，我们必须重写接口中的CompareTo()方法，这个方法用来比较两个对象的大小，因为方法本身并不知道我我们会根据对象的哪个属性来比较两个对象的大小，因此在这个方法中，我们可以定义我们自己的比较规则。

在上述的代码中，我们调用了Double类的比较方法来比较两个对象的speed属性的大小，如果调用方法的Car对象的speed属性值比方法参数传进来的Car对象的speed值大就返回1，相等就返回0，小于就返回-1。当然，我们也可以自己手写这个部分，无非就是if else判断的事。

之所以有两种写法，是因为第一种使用了泛型，第二种使用了对象的强制转换，可以看到，当我们使用泛型的时候，在调用对象的时候就已经确定了使用接口的时候用的是哪一种对象，因此就不用把对象类型强制转换为我们想要的类型了。而第二种我们没有使用泛型，因此就需要把参数传进来的对象强制转换成我们想要的类型然后再进行操作。推荐使用第一种写法。

接下来，我们在main方法中构建了一个Car类型的数组，然后直接调用Arrays.sort()方法传进数组作为参数就可以对数组进行排序了。

这种方法比较方便，快捷，在性能方面也有不错的表现，本人亲测在排序20万个对象的时候花费差不多200ms左右的时间。

当然，这种方法主要图的是方便，当我们需要排序大量的数据的时候，还是应该结合自己数据的特性来具体选择一种排序方式自己写。

浅谈Arrays.sort()原理

首先先来看一下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() {

@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, 9QpvTtGqDjK8, 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.对重复数据进行了优化处理，避免了不必要交换和递归。

{

for(int j=0;j

{

if(a[j].getSpeed()>a[j+1].getSpeed())//交换操作

{

Car temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

}

}

}

这样写确实能实现了效果，但是未必性能很好，由于是自己写的，写起来也会比较麻烦，下面的方法会更好

Arrays.sort()方法

我们先来看看用Array.sort()方法实现对车辆排序的代码：

其中，Car这个类有两种写法：

第一种写法：

public class Car implements Comparable{

private double speed;

public Car(double speed) {

this.speed = speed;

}

public double getSpeed() {

return speed;

}

public void setSpeed(double speed) {

this.speed = speed;

}

@Override

public int compareTo(Car newCar) {

return Double.compare(this.getSpeed(),newCar.getSpeed());

}

}

第二种写法

public class Car implements Comparable{

private double speed;

public Car(double speed) {

this.speed = speed;

}

public double getSpeed() {

return speed;

}

public void setSpeed(double speed) {

this.speed = speed;

}

@Override

public int compareTo(Object newCar) {

return Double.compare(this.getSpeed(),((Car)newCar).getSpeed());

}

}

main方法：

public class Test8 {

public static void main(String[] args) {

Car[] carList = new Car[3];

carList[0] = new Car(30);

carList[1] = new Car(10);

carList[2] = new Car(55);

Arrays.sort(carList);

for(Car c:carList)

{

System.out.println(c.getSpeed());

}

}

}

输出结果：

解析：

顾名思义，Arrays类的sort()方法是对一个数组进行排序的方法，sort()方法的参数是一个对象数组，也就是要排序的那个数组，但是有些特别的是，这个对象数组中存储的对象的类必须实现了Comparable接口。

Comparable接口是用来比较大小的，要实现这个接口，我们必须重写接口中的CompareTo()方法，这个方法用来比较两个对象的大小，因为方法本身并不知道我我们会根据对象的哪个属性来比较两个对象的大小，因此在这个方法中，我们可以定义我们自己的比较规则。

在上述的代码中，我们调用了Double类的比较方法来比较两个对象的speed属性的大小，如果调用方法的Car对象的speed属性值比方法参数传进来的Car对象的speed值大就返回1，相等就返回0，小于就返回-1。当然，我们也可以自己手写这个部分，无非就是if else判断的事。

之所以有两种写法，是因为第一种使用了泛型，第二种使用了对象的强制转换，可以看到，当我们使用泛型的时候，在调用对象的时候就已经确定了使用接口的时候用的是哪一种对象，因此就不用把对象类型强制转换为我们想要的类型了。而第二种我们没有使用泛型，因此就需要把参数传进来的对象强制转换成我们想要的类型然后再进行操作。推荐使用第一种写法。

接下来，我们在main方法中构建了一个Car类型的数组，然后直接调用Arrays.sort()方法传进数组作为参数就可以对数组进行排序了。

这种方法比较方便，快捷，在性能方面也有不错的表现，本人亲测在排序20万个对象的时候花费差不多200ms左右的时间。

当然，这种方法主要图的是方便，当我们需要排序大量的数据的时候，还是应该结合自己数据的特性来具体选择一种排序方式自己写。

浅谈Arrays.sort()原理

首先先来看一下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() {

@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, 9QpvTtGqDjK8, 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.对重复数据进行了优化处理，避免了不必要交换和递归。

{

if(a[j].getSpeed()>a[j+1].getSpeed())//交换操作

{

Car temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

}

}

}

这样写确实能实现了效果，但是未必性能很好，由于是自己写的，写起来也会比较麻烦，下面的方法会更好

Arrays.sort()方法

我们先来看看用Array.sort()方法实现对车辆排序的代码：

其中，Car这个类有两种写法：

第一种写法：

public class Car implements Comparable{

private double speed;

public Car(double speed) {

this.speed = speed;

}

public double getSpeed() {

return speed;

}

public void setSpeed(double speed) {

this.speed = speed;

}

@Override

public int compareTo(Car newCar) {

return Double.compare(this.getSpeed(),newCar.getSpeed());

}

}

第二种写法

public class Car implements Comparable{

private double speed;

public Car(double speed) {

this.speed = speed;

}

public double getSpeed() {

return speed;

}

public void setSpeed(double speed) {

this.speed = speed;

}

@Override

public int compareTo(Object newCar) {

return Double.compare(this.getSpeed(),((Car)newCar).getSpeed());

}

}

main方法：

public class Test8 {

public static void main(String[] args) {

Car[] carList = new Car[3];

carList[0] = new Car(30);

carList[1] = new Car(10);

carList[2] = new Car(55);

Arrays.sort(carList);

for(Car c:carList)

{

System.out.println(c.getSpeed());

}

}

}

输出结果：

解析：

顾名思义，Arrays类的sort()方法是对一个数组进行排序的方法，sort()方法的参数是一个对象数组，也就是要排序的那个数组，但是有些特别的是，这个对象数组中存储的对象的类必须实现了Comparable接口。

Comparable接口是用来比较大小的，要实现这个接口，我们必须重写接口中的CompareTo()方法，这个方法用来比较两个对象的大小，因为方法本身并不知道我我们会根据对象的哪个属性来比较两个对象的大小，因此在这个方法中，我们可以定义我们自己的比较规则。

在上述的代码中，我们调用了Double类的比较方法来比较两个对象的speed属性的大小，如果调用方法的Car对象的speed属性值比方法参数传进来的Car对象的speed值大就返回1，相等就返回0，小于就返回-1。当然，我们也可以自己手写这个部分，无非就是if else判断的事。

之所以有两种写法，是因为第一种使用了泛型，第二种使用了对象的强制转换，可以看到，当我们使用泛型的时候，在调用对象的时候就已经确定了使用接口的时候用的是哪一种对象，因此就不用把对象类型强制转换为我们想要的类型了。而第二种我们没有使用泛型，因此就需要把参数传进来的对象强制转换成我们想要的类型然后再进行操作。推荐使用第一种写法。

接下来，我们在main方法中构建了一个Car类型的数组，然后直接调用Arrays.sort()方法传进数组作为参数就可以对数组进行排序了。

这种方法比较方便，快捷，在性能方面也有不错的表现，本人亲测在排序20万个对象的时候花费差不多200ms左右的时间。

当然，这种方法主要图的是方便，当我们需要排序大量的数据的时候，还是应该结合自己数据的特性来具体选择一种排序方式自己写。

浅谈Arrays.sort()原理

首先先来看一下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() {

@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, 9QpvTtGqDjK8, 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.对重复数据进行了优化处理，避免了不必要交换和递归。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。