首页 > 编程语言 >Java 中的各种排序:详细教程

Java 中的各种排序:详细教程

时间:2024-08-30 19:51:28浏览次数:15  
标签:Customer sort 教程 Java Arrays int 排序

1. 前言

本文通过许多代码示例逐步解释如何对 Java 中原始数据类型(intlongdouble等)和任何类的对象进行排序。

具体来说,本文主要回答了以下问题:

  • 如何对 Java 中原始数据类型的数组进行排序?
  • 如何对 Java 中的对象数组和列表进行排序?
  • 如何在 Java 中并行排序?
  • JDK 内部使用哪些排序算法?

2. Java 中可以对什么进行排序?

以下数据类型可以用 Java 的内置工具进行排序:

  • 原始数据类型的数组(int[]、long[]、double[]等)。
  • 实现Comparable接口的对象数组和列表。
  • 任意类的对象数组和列表,指定一个比较器,即实现comparator接口的附加对象(或相应的Lambda表达式)。

3. Arrays.sort() – 对原始数据类型进行排序

该类java.util.Arrays为所有原始数据类型(除)提供了排序方法boolean

  • static void sort(byte[] a)
  • static void sort(char[] a)
  • static void sort(double[] a)
  • static void sort(float[] a)
  • static void sort(int[] a)
  • static void sort(long[] a)
  • static void sort(short[] a)
3.1 示例:对 int 数组进行排序

下面的示例显示如何对int数组进行排序然后将其打印到控制台:

int[] a = {4, 8, 5, 9, 2, 3, 1, 7, 6};
Arrays.sort(a);
System.out.println(Arrays.toString(a));

 这个简短的程序的输出是:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

对于上述每种数据类型(int、long、double等),都存在一个重载方法,该方法仅对数组的一个子集进行排序,例如:

  • static void sort(int[] a, int fromIndex, int toIndex)

以下示例仅对数组的前五个元素进行排序:

int[] a = {4, 8, 5, 9, 2, 3, 1, 7, 6};
Arrays.sort(a, 0, 5);
System.out.println(Arrays.toString(a));

该程序打印以下内容:

[2, 4, 5, 8, 9, 3, 1, 7, 6]

4. 如何对 Java 对象进行排序

原始数据类型按其自然顺序排序。因此,我们的示例数组[4, 8, 5, 9, 2, 3, 1, 7, 6]排序后变为[1, 2, 3, 4, 5, 6, 7, 8, 9]

但是物体是按照什么顺序排序的呢?

4.1 对整数和字符串数组进行排序

每个 Java 开发人员都直观地了解IntegerString数组是如何排序的:

Integer[] a = {4, 8, 5, 9, 2, 3, 1, 7, 6};
Arrays.sort(a);
System.out.println(Arrays.toString(a));

我们还得到:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

让我们对一些名字进行排序:

String[] names = {"Susan", "Thomas", "Judith", "Daniel", "Eva", "Ben",
      "Antonia", "Paul"};
Arrays.sort(names);
System.out.println(Arrays.toString(names));

结果正如预期:

[Antonia, Ben, Daniel, Eva, Judith, Paul, Susan, Thomas]

因此,Integer对象的排序方式与int基元相同。字符串按字母顺序排序。

4.2 对自定义类的对象进行排序

但是你如何对你自己创建的Customer类进行排序?或者Invoice

让我们尝试一下!这是我们的Customer课程:

public class Customer {
  private int id;
  private String firstName;
  private String lastName;

  public Customer(int id, String firstName, String lastName) {
    this.id = id;
    this.firstName = firstName;
    this.lastName = lastName;
  }

  @Override
  public String toString() {
    return "Customer{" +
          "id=" + id +
          ", firstName='" + firstName + ''' +
          ", lastName='" + lastName + ''' +
          '}';
  }

我们尝试对一些客户进行分类Arrays.sort()

Customer[] customers = {
      new Customer(43423, "Elizabeth", "Mann"),
      new Customer(10503, "Phil", "Gruber"),
      new Customer(61157, "Patrick", "Sonnenberg"),
      new Customer(28378, "Marina", "Metz"),
      new Customer(57299, "Caroline", "Albers")
};
Arrays.sort(customers);
System.out.println(Arrays.toString(customers));

Java 对此尝试做出以下错误消息响应:

线程“main”中的异常 java.lang.ClassCastException
eu.happycoders.sorting.Customer 不能转换为类 java.lang.Comparable

如果没有附加信息,Java 不知道如何对Customer对象进行排序。我们如何提供这些信息?

5. 使用 Comparable 和 Comparator 进行排序

该接口java.lang.Comparable定义了一个方法:

  • public int compareTo(T o)

排序算法会调用该方法来检查一个对象是否小于等于大于另一个对象。根据此情况,该方法必须返回负数、0 或正数。

Integer(当您查看和的源代码时String,您将看到两者都实现了Comparable接口和compareTo()方法。)

我们希望按客户编号对客户进行排序。因此,我们必须扩展该类,如下所示(为了清晰起见,Customer我省略了构造函数和方法):toString()

public class Customer implements Comparable<Customer> {
  private int id;
  private String firstName;
  private String lastName;

  // Constructor and toString method omitted

  @Override
  public int compareTo(Customer o) {
    return this.id < o.id ? -1 : (this.id == o.id ? 0 : 1);
  }
}

compareTo()从方法角度来看其功能:

  • 如果我的客户编号小于你的,则返回-1;
  • 如果我们的客户编号相同,则返回 0
  • 否则返回 1。

如果使用方法,它会变得更短一些Integer.compare()。它以完全相同的方式比较两个 ID:

@Override
public int compareTo(Customer o) {
  return Integer.compare(this.id, o.id);
}

我们现在可以轻松地对扩展Customer类进行排序(这里再次给出上面的客户排序示例,因此您不必向上滚动):

Customer[] customers = {
      new Customer(43423, "Elizabeth", "Mann"),
      new Customer(10503, "Phil", "Gruber"),
      new Customer(61157, "Patrick", "Sonnenberg"),
      new Customer(28378, "Marina", "Metz"),
      new Customer(57299, "Caroline", "Albers")
};
Arrays.sort(customers);
System.out.println(Arrays.toString(customers));

这次程序运行时没有错误,并打印以下内容(为了清楚起见,我手动插入了换行符):

[Customer{id=10503, firstName='Phil', lastName='Gruber'},
 Customer{id=28378, firstName='Marina', lastName='Metz'},
 Customer{id=43423, firstName='Elizabeth', lastName='Mann'},
 Customer{id=57299, firstName='Caroline', lastName='Albers'},
 Customer{id=61157, firstName='Patrick', lastName='Sonnenberg'}]

我们现在按照要求按照客户编号对客户进行排序。

但是如果我们想按姓名而不是数字对客户进行排序怎么办?我们compareTo()只需实现一次。我们是否必须永远决定一个排序顺序?

这就是界面Comparator发挥作用的地方,我将在下一节中描述。

5.1 如何使用比较器进行排序

通过Customer.compareTo()方法,我们定义了所谓的客户“自然顺序”。通过接口Comparator,我们可以为类定义任意数量的附加排序顺序。

与方法类似compareTo()Comparator接口定义了以下方法:

  • int compare(T o1, T o2)

调用此方法来检查 object 是否o1小于等于大于objecto2因此,此方法还必须返回负数、0 或正数。

从 Java 8 开始,我们可以使用 优雅地创建一个比较器Comparator.comparing()。使用以下代码,我们可以先按姓氏对客户进行排序,然后按名字对客户进行排序:

Arrays.sort(customers,
      Comparator.comparing(Customer::getLastName)
            .thenComparing(Customer::getFirstName));

如您所见,您可以几乎用自然语言写下应如何对客户进行排序。

我们还可以将比较器存储在类中的常量中,Customer以便在其他地方重复使用它:

public static final Comparator<Customer> NAME_COMPARATOR = Comparator
    .comparing(Customer::getLastName)
    .thenComparing(Customer::getFirstName);

然后我们会对客户进行如下排序:

Arrays.sort(customers, Customer.NAME_COMPARATOR);

6. 在 Java 中对List列表进行排序

到目前为止,我们仅使用了该类的以下两种方法java.util.Arrays来对对象进行排序:

  • static void sort(Object[] a)– 根据物体的自然顺序对其进行排序,
  • static void sort(T[] a, Comparator<? super T> c)– 使用提供的比较器对对象进行排序。

我们经常将对象存储在列表中而不是数组中。要对它们进行排序,有两种方法(自 Java 8 起):

6.1 使用 Collections.Sort() 对列表进行排序

直到 Java 7 为止,我们必须使用该方法Collections.sort()对列表进行排序。

在下面的例子中,我们要再次对客户进行排序,首先按客户编号(即根据他们的“自然顺序”):

List<Customer> customers = new ArrayList<>(List.of(
      new Customer(43423, "Elizabeth", "Mann"),
      new Customer(10503, "Phil", "Gruber"),
      new Customer(61157, "Patrick", "Sonnenberg"),
      new Customer(28378, "Marina", "Metz"),
      new Customer(57299, "Caroline", "Albers")
));
Collections.sort(customers);
System.out.println(customers);

与前面的示例一样,程序按客户编号排序打印客户。

为什么我在示例中创建两个列表?一个带有List.of(),另一个带有new ArrayList<>()

List.of()是创建列表的最优雅的方式。但是,创建的列表是不可变的(这对于大多数用例来说都是有意义的List.of()),因此无法对其进行排序。因此,我将其传递给的构造函数ArrayList,该构造函数会将其转换为可变列表。诚然:这不是性能最高的解决方案,但它使代码简洁明了。

顺便说一句,Collections.sort()在编译时已经检查(与Arrays.sort())传递的列表是否由实现的对象组成Comparable

6.2 使用 Collections.Sort() 和比较器对列表进行排序

您还可以在调用时指定比较器Collections.sort()。以下代码行按客户姓名对客户进行排序:

Collections.sort(customers, Customer.NAME_COMPARATOR);

6.3 使用 List.Sort() 对列表进行排序

从 Java 8 开始,(得益于接口中的默认方法)可以直接使用 对列表进行排序。必须始终指定List.sort()比较器:

customers.sort(Customer.NAME_COMPARATOR);

但是,比较器也可以null根据列表的自然顺序对其进行排序:

customers.sort(null);

同样,如果传递的列表包含不实现Comparable的对象,我们会得到ClassCastException。

7. 并行排序数组

从 Java 8 开始,类中的每个排序方法java.util.Arrays都提供并行变体。它们将排序工作从定义的数组大小(从 Java 8 到 Java 13 为 8,192 个元素;从 Java 14 开始为 4,097 个元素)分配到多个 CPU 核心。示例:

  • static void parallelSort(double[] a)

double以下示例测量对 1 亿个值进行排序所需的时间,一次使用Arrays.sort(),一次使用Arrays.parallelSort()

public class DoubleArrayParallelSortDemo {
  private static final int NUMBER_OF_ELEMENTS = 100_000_000;

  public static void main(String[] args) {
    for (int i = 0; i < 5; i++) {
      sortTest("sort", Arrays::sort);
      sortTest("parallelSort", Arrays::parallelSort);
    }
  }

  private static void sortTest(String methodName, Consumer<double[]> sortMethod) {
    double[] a = createRandomArray(NUMBER_OF_ELEMENTS);
    long time = System.currentTimeMillis();
    sortMethod.accept(a);
    time = System.currentTimeMillis() - time;
    System.out.println(methodName + "() took " + time + " ms");
  }

  private static double[] createRandomArray(int n) {
    ThreadLocalRandom current = ThreadLocalRandom.current();
    double[] a = new double[n];
    for (int i = 0; i < n; i++) {
      a[i] = current.nextDouble();
    }
    return a;
  }
}

我的系统(配备 Core i7-8750H 的 DELL XPS 15)显示以下读数:

sort() took 9596 ms
parallelSort() took 2186 ms
sort() took 9232 ms
parallelSort() took 1835 ms
sort() took 8994 ms
parallelSort() took 1917 ms
sort() took 9152 ms
parallelSort() took 1746 ms
sort() took 8899 ms
parallelSort() took 1757 ms

第一次调用会花费更长的时间,因为 HotSpot 编译器需要一些时间来优化代码。

之后,您可以看到并行排序比顺序排序快大约五倍。对于六核来说,这是一个非常好的结果,因为并行化自然会带来一定的开销。

8. Java开发工具包(JDK)中的排序算法

JDK根据手头的任务应用不同的排序算法:

  • 如果要对超过64个字节或超过1750个短字符或字符进行排序,则对byte[]、short[]和char[]进行计数排序。
  • 双枢轴快速排序,用于使用Arrays.sort()对原始数据类型进行排序。这是Quicksort的优化变体,结合了插入排序和计数排序。该算法对许多数据集实现了O(n log n)的时间复杂度,而其他Quicksort实现通常会回落到O(n²)。
  • Timsort(与插入排序相结合的优化自然合并排序)用于所有其他对象。

对于并行排序,使用以下算法:

  • 字节、短字符、字符从不并行排序。
  • 对于其他基本数据类型,使用快速排序、合并排序、插入排序和Heapsort的组合。
  • Timsort也用于对象——然而,并行变体仅适用于超过8192个元素的列表大小;下面,使用单螺纹变体。否则,开销将大于性能增益。

9. 总结

在本文中,我们一起学习了如何对 Java 中的原始数据类型和对象进行排序,以及 JDK 内部使用哪些自带的排序方法.

总的来说,本文主要对以下排序进行的详细介绍:

  1. 如何对 Java 中原始数据类型的数组进行排序?
  2. 如何对 Java 中的对象数组和列表进行排序?
  3. 如何在 Java 中并行排序?
  4. JDK 内部使用哪些排序算法?

欢迎大家拜读,谢谢大家!

标签:Customer,sort,教程,Java,Arrays,int,排序
From: https://blog.csdn.net/lilinhai548/article/details/141689040

相关文章

  • JavaScript - 闭包
    使用场景数据封装闭包允许创建私有变量,这些变量在函数外部无法直接访问。通过闭包,可以创建具有私有状态的对象,从而实现数据封装。例如:functioncreateCounter(){letcount=0;//count是私有变量returnfunction(){count++;returncount;};}const......
  • 发红包案例(java)
    User类创建publicclassUser{privateStringname;privateintmoney;publicUser(){}publicUser(Stringname,intmoney){this.name=name;this.money=money;}publicvoidshow(){System.out.println(&qu......
  • 【Linux】开源的系统监控和故障排除工具Sysdig:用于系统监控、故障排除和安全审计,从下
    Sysdig是一个开源的系统监控和故障排除工具,可以捕获和分析系统调用,帮助你深入了解系统的运行状态。无论是开发人员、运维工程师还是安全专家,Sysdig都是进行系统监控、故障排除和安全审计的理想工具。本文将详细介绍Sysdig的安装、基本使用方法以及一些高级用法,并通过具......
  • Java根据经纬度计算两个坐标之间的距离(含SQL计算)
    最近接到两个需求,一个是通过小程序扫码开门的,我这边主要就是根据用户定位判断用户离扫码店铺距离小于多少米的时候才可以调远程调开门接口,另外一个就是获取用户周围有哪些店铺。需求很简单,就是根据定位获取的经度维度计算两个点之间的球面距离,这里我们主要采用Haversine公......
  • LTspice使用教程,LTspice仿真教程资源大全
      LTspice简介 LTspice是英文SimulationProgramwithIntegratedCircuitEmphasis的缩写,意思是集成电路通用模拟程序。是ADI旗下的一款免费软件,很多国外的工程师、教授、学生基本用的都是LTspice,感觉应该是最好用的一款,也是教程在国内普及的比较好的一款仿真软件......
  • javascript 检测 麦克风状态
    <htmllang="zh"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>麦克风监听示例<style>body......
  • 打包exe_java
    主要实现步骤1,将代码打包成jar包。2,整合资源文件3,将jar包打包成exe4,将jdk、资源文件、jar包转换后的exe三者再次打包成最终的exe。准备软件1,Idea:将代码打包成jar包(java形式的压缩包)2,exe4j:将jar包转换成exe的工具。3,innosetup:将游戏用到的图片,Java的......
  • LTSPICE仿真教程,LTSPICE使用教程汇总
    LTspice介绍LTspice由亚德诺半导体(ADI)推出。LTspice是一款功能强大的SPICE仿真器软件,具备原理图捕获图形界面,能够探测原理图并生成仿真结果,用户可通过其内置的波形查看器轻松探索仿真结果。与其他SPICE解决方案相比,LTspice的增强功能和模型极大地提升了模拟电路仿真......
  • Java后端分布式系统的服务调用链路管理:服务目录与服务市场
    Java后端分布式系统的服务调用链路管理:服务目录与服务市场大家好,我是微赚淘客返利系统3.0的小编,是个冬天不穿秋裤,天冷也要风度的程序猿!在Java后端分布式系统中,服务调用链路的管理是确保微服务架构良好运作的关键。服务目录提供了服务的注册与发现机制,而服务市场则为服务的共享与......
  • 基于javaweb的smile旅行社管理系统的设计与实现 毕业设计-附源码02508
    摘 要随着旅游行业的蓬勃发展,旅行社作为连接旅游资源和游客的桥梁,其管理效率和服务质量直接影响着客户满意度和企业竞争力。为了更好地满足市场需求,提升旅行社的管理水平和运营效率,设计与实现一套高效、稳定的旅行社管理系统显得尤为重要。基于JavaWeb的Smile旅行社管......