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

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

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

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

假如我们现在有一个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<a.length-1;i++)//a为一个存储了很多Car对象的数组
{
	for(int j=0;j<a.length-i-1;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<Car>{
	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<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.对重复数据进行了优化处理,避免了不必要交换和递归。

以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • JAVA基于Arrays.sort()实现数组升序和降序

    java中对数组进行排序 使用Array.sort() 这个默认是升序 @Test public void index4(){ int scores[] = new int[]{1,2,3,89,4}; Arrays.sort(scores); for (int i:scores ) { System.out.println(i); } } 如果想降序怎么办呢? 使用:Arrays.sort(scores,Collections.reverseOrder()); 需要注意的是 不能使用基本类型(

  • Java Arrays.sort()用法详解

    Java的Arrays类中有一个sort()方法,该方法是Arrays类的静态方法,在需要对数组进行排序时,非常的好用. 但是sort()的参数有好几种,下面我就为大家一一介绍,这几种形式的用法. 1.Arrays.sort(int[] a) 这种形式是对一个数组的所有元素进行排序,并且是按从小到大的顺序. 举例如下: import java.util.Arrays; public class Main { public static void main(String[] args) { int

  • java中的arrays.sort()代码详解

    Arrays.sort(T[], Comparator < ? super T > c) 方法用于对象数组按用户自定义规则排序. 官方Java文档只是简要描述此方法的作用,并未进行详细的介绍,本文将深入解析此方法. 1. 简单示例 sort方法的使用非常的简单明了,下面的例子中,先定义一个比较Dog大小的Comparator,然后将其实例对象作为参数传给sort方法,通过此示例,你应该能够快速掌握Arrays.sort()的使用方法. import java.util.Arrays; impo

  • Java Arrays.sort和Collections.sort排序实现原理解析

    1.使用 排序 2.原理 事实上Collections.sort方法底层就是调用的array.sort方法,而且不论是Collections.sort或者是Arrays.sort方法, 跟踪下源代码吧,首先我们写个demo public static void main(String[] args) { List<String> strings = Arrays.asList("6", "1", "3", "1",

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

    目录 使用Arrays.sort()方法给对象排序 麻烦的方法 Arrays.sort()方法 浅谈Arrays.sort()原理 例子1 基础知识点 例子2 双轴快排 另外参考了其他博文,算法思路如下 使用Arrays.sort()方法给对象排序 当我们给一个整型数组或者浮点型之类的数组排序的时候,很简单就可以达到我们排序的目的,无非是排序算法的问题.那么,如果我们现在想根据对象的一个属性值给一个对象数组进行排序呢? 假如我们现在有一个Car类型,Car类中有一个double型的speed属性

  • Java的Arrays.sort()方法排序算法实例分析

    暂时网上看过很多JDK8中Arrays.sort的底层原理,有些说是插入排序,有些说是归并排序,也有说大于域值用计数排序法,否则就使用插入排序...其实不全对.让我们分析个究竟: // Use Quicksort on small arrays if (right - left < QUICKSORT_THRESHOLD) { //QUICKSORT_THRESHOLD = 286 sort(a, left, right, true); return; } 数组一进来,会碰到第一个阀值QUICK

  • 用Java集合中的Collections.sort方法如何对list排序(两种方法)

    第一种是list中的对象实现Comparable接口,如下: /** * 根据order对User排序 */ public class User implements Comparable <user> { private String name; private Integer order; public String getName() { return name; } public void setName(String name) { this.name = name; } publi

  • 深入理解java中Arrays.sort()的用法

    Java的Arrays类中有一个sort()方法,该方法是Arrays类的静态方法,在需要对数组进行排序时,非常的好用. 但是sort()的参数有好几种,基本上是大同小异,下面是以int型数组为例的Arrays.sort()的典型用法 import java.util.Arrays; import java.util.Comparator; /** * Arrays.sort()排序 */ public class SortTest { public static void main(Strin

  • Arrays.sort如何实现降序排序

    目录 Arrays.sort实现降序排序 1.Collections的reverseOrder 2.利用Comparator接口复写compare Arrays.sort底层原理 概述 案例 总结 Arrays.sort实现降序排序 在调用Arrays.sort()对数组进行排序时,默认是升序排序的,如果想让数组降序排序,有下面两种方法: 1.Collections的reverseOrder import java.util.*;   public class Main {     public

  • jQuery实现使用sort方法对json数据排序的方法

    本文实例讲述了jQuery实现使用sort方法对json数据排序的方法.分享给大家供大家参考,具体如下: 如何对后台返回过来的json数据按照数据中的某一项进行排序呢. 首先看一下排序前的json数据: { "result":[ { "cid":1, "name":"aaa", "price":1000 },{ "cid":2, "name":"bbb&qu

  • JS sort方法基于数组对象属性值排序

    sort方法接收一个函数作为参数,这里嵌套一层函数用来接收对象属性名,其他部分代码与正常使用sort方法相同. var arr = [ {name:'zopp',age:0}, {name:'gpp',age:18}, {name:'yjj',age:8} ]; function compare(property){ return function(a,b){ var value1 = a[property]; var value2 = b[property]; return value1 -

  • Java List的sort()方法改写compare()实现升序,降序,倒序的案例

    本文旨在通过重写Comparator接口的compare()方法实现对List的升序.降序.倒序排序. 首先明确一点: compare(Integer o1, Integer o2){}中,o1代表的是List容器中的后一个元素,o2代表的是List容器中的前一个元素! 通过以下例子可以清晰了解这一点: public static void main(String[] args) { List<Integer> list = new ArrayList<Integer>(); li

  • Java中Arrays.asList()方法详解及实例

    Arrays.asList() 是将数组作为列表. 问题来源于: public class Test { public static void main(String[] args) { int[] a = {1, 2, 3, 4}; List list = Arrays.asList(a); System.out.println(list.size()); //1 } } 期望的输出是 list 里面也有4个元素,也就是 size 为4,然而结果是1. 原因如下: 在 Arrays.asLis

随机推荐