书签

在Java中排序

评论 0 浏览 0 2016-11-30

1.概述

本文将说明如何在Java 7和Java 8中对Array、List、Set和Map应用排序。

2.用Array进行排序

让我们先用Arrays.sort() 方法来对整数数组进行排序。

我们将在一个@BeforejUnit方法中定义以下int数组。

@Before
public void initVariables () {
    toSort = new int[] 
      { 5, 1, 89, 255, 7, 88, 200, 123, 66 }; 
    sortedInts = new int[] 
      {1, 5, 7, 66, 88, 89, 123, 200, 255};
    sortedRangeInts = new int[] 
      {5, 1, 89, 7, 88, 200, 255, 123, 66};
    ...
}

2.1.对完整数组进行排序

现在让我们来使用简单的Array.sort() API。

@Test
public void givenIntArray_whenUsingSort_thenSortedArray() {
    Arrays.sort(toSort);

    assertTrue(Arrays.equals(toSort, sortedInts));
}

未排序的数组现在已经完全排序了。

[1, 5, 7, 66, 88, 89, 123, 200, 255]

如官方 JavaDoc 中所述，Arrays.sort 在基元 上使用双枢轴快速排序。它提供 O(n log(n)) 性能，通常比传统（单轴）快速排序实现更快。但是，它使用 对象数组的合并排序算法。

2.2.对数组的一部分进行排序

Arrays.sort还有一个sort APIs – 我们将在这里讨论这个问题。

Arrays.sort(int[] a, int fromIndex, int toIndex)

这将只对数组的一部分进行排序，即在两个索引之间进行排序。

让我们看一下一个快速的例子。

@Test
public void givenIntArray_whenUsingRangeSort_thenRangeSortedArray() {
    Arrays.sort(toSort, 3, 7);
 
    assertTrue(Arrays.equals(toSort, sortedRangeInts));
}

排序将只在下面的子数组元素上进行（toIndex将是排他性的）。

[255, 7, 88, 200]

结果排序后的子数组与主数组包括在一起，将是。

[5, 1, 89, 7, 88, 200, 255, 123, 66]

2.3 Java 8 Arrays.sort 与Arrays.parallelSort的对比

Java 8带有一个新的API – parallelSort – 具有与Arrays.sort() API类似的签名。

@Test 
public void givenIntArray_whenUsingParallelSort_thenArraySorted() {
    Arrays.parallelSort(toSort);
 
    assertTrue(Arrays.equals(toSort, sortedInts));
}

在parallelSort()的背后，它把数组分成不同的子数组（按照parallelSort算法的粒度）。每个子数组在不同的线程中用Arrays.sort()进行排序，这样sort可以以并行的方式执行，最后合并为一个排序的数组。

请注意，ForJoin公共池被用来执行这些并行任务，然后合并结果。

当然，Arrays.parallelSort的结果要和Array.sort一样，只是利用了多线程的问题。

最后，在Arrays.parallelSort中也有类似的API Arrays.sort的变体。

Arrays.parallelSort (int [] a, int fromIndex, int toIndex);

3.对一个List进行排序

现在让我们使用Collections.sort()API中的java.utils.Collections – 来对一个List的整数进行排序。

@Test
public void givenList_whenUsingSort_thenSortedList() {
    List<Integer> toSortList = Ints.asList(toSort);
    Collections.sort(toSortList);

    assertTrue(Arrays.equals(toSortList.toArray(), 
    ArrayUtils.toObject(sortedInts)));
}

排序前的List将包含以下元素：

[5, 1, 89, 255, 7, 88, 200, 123, 66]

自然地，排序后：

[1, 5, 7, 66, 88, 89, 123, 200, 255]

正如Oracle JavaDoc中提到的Collections.Sort，它使用了修改过的mergesort，并提供了有保证的n log(n)性能。

4.对一个Set集进行排序

接下来，让我们使用Collections.sort()来对一个LinkedHashSet进行排序。

我们使用LinkedHashSet，因为它可以保持插入顺序。

请注意，为了在Collections中使用sort API – 我们首先将集合包裹在一个列表中。

@Test
public void givenSet_whenUsingSort_thenSortedSet() {
    Set<Integer> integersSet = new LinkedHashSet<>(Ints.asList(toSort));
    Set<Integer> descSortedIntegersSet = new LinkedHashSet<>(
      Arrays.asList(new Integer[] 
        {255, 200, 123, 89, 88, 66, 7, 5, 1}));
        
    List<Integer> list = new ArrayList<Integer>(integersSet);
    Collections.sort(Comparator.reverseOrder());
    integersSet = new LinkedHashSet<>(list);
        
    assertTrue(Arrays.equals(
      integersSet.toArray(), descSortedIntegersSet.toArray()));
}

Comparator.reverseOrder() 方法将自然排序所强加的排序颠倒过来。

5.排序Map

在本节中，我们将开始研究对 Map 进行排序——既可以按键也可以按值。

让我们首先定义一下我们要排序的Map。

@Before
public void initVariables () {
    ....
    HashMap<Integer, String> map = new HashMap<>();
    map.put(55, "John");
    map.put(22, "Apple");
    map.put(66, "Earl");
    map.put(77, "Pearl");
    map.put(12, "George");
    map.put(6, "Rocky");
    ....
}

5.1 按键对Map进行排序

我们现在要从HashMap中提取keys和values条目，并根据本例中的键值对其进行排序。

@Test
public void givenMap_whenSortingByKeys_thenSortedMap() {
    Integer[] sortedKeys = new Integer[] { 6, 12, 22, 55, 66, 77 };

    List<Map.Entry<Integer, String>> entries 
      = new ArrayList<>(map.entrySet());
    Collections.sort(entries, new Comparator<Entry<Integer, String>>() {
        @Override
        public int compare(
          Entry<Integer, String> o1, Entry<Integer, String> o2) {
            return o1.getKey().compareTo(o2.getKey());
        }
    });
    Map<Integer, String> sortedMap = new LinkedHashMap<>();
    for (Map.Entry<Integer, String> entry : entries) {
        sortedMap.put(entry.getKey(), entry.getValue());
    }
        
    assertTrue(Arrays.equals(sortedMap.keySet().toArray(), sortedKeys));
}

请注意我们在复制基于键的排序条目时如何使用LinkedHashMap （因为HashSet不保证键的顺序）。

排序前的Map：

[Key: 66 , Value: Earl] 
[Key: 22 , Value: Apple] 
[Key: 6 , Value: Rocky] 
[Key: 55 , Value: John] 
[Key: 12 , Value: George] 
[Key: 77 , Value: Pearl]

按键排序后的Map：

[Key: 6 , Value: Rocky] 
[Key: 12 , Value: George] 
[Key: 22 , Value: Apple] 
[Key: 55 , Value: John] 
[Key: 66 , Value: Earl] 
[Key: 77 , Value: Pearl]

5.2.按照值对Map进行排序

这里我们将比较HashMap的值，以根据HashMap的值进行排序：

@Test
public void givenMap_whenSortingByValues_thenSortedMap() {
    String[] sortedValues = new String[] 
      { "Apple", "Earl", "George", "John", "Pearl", "Rocky" };

    List<Map.Entry<Integer, String>> entries 
      = new ArrayList<>(map.entrySet());
    Collections.sort(entries, new Comparator<Entry<Integer, String>>() {
        @Override
        public int compare(
          Entry<Integer, String> o1, Entry<Integer, String> o2) {
            return o1.getValue().compareTo(o2.getValue());
        }
    });
    Map<Integer, String> sortedMap = new LinkedHashMap<>();
    for (Map.Entry<Integer, String> entry : entries) {
        sortedMap.put(entry.getKey(), entry.getValue());
    }
        
    assertTrue(Arrays.equals(sortedMap.values().toArray(), sortedValues));
}

排序前的Map：

[Key: 66 , Value: Earl] 
[Key: 22 , Value: Apple] 
[Key: 6 , Value: Rocky] 
[Key: 55 , Value: John] 
[Key: 12 , Value: George] 
[Key: 77 , Value: Pearl]

按值排序后的Map：

[Key: 22 , Value: Apple] 
[Key: 66 , Value: Earl] 
[Key: 12 , Value: George] 
[Key: 55 , Value: John] 
[Key: 77 , Value: Pearl] 
[Key: 6 , Value: Rocky]

6.对自定义对象进行排序

现在让我们使用自定义对象：

public class Employee implements Comparable {
    private String name;
    private int age;
    private double salary;

    public Employee(String name, int age, double salary) {
        ...
    }

    // standard getters, setters and toString
}

在下面的章节中，我们将使用下面的Employee数组来进行排序的例子：

@Before
public void initVariables () {
    ....    
    employees = new Employee[] { 
      new Employee("John", 23, 5000), new Employee("Steve", 26, 6000), 
      new Employee("Frank", 33, 7000), new Employee("Earl", 43, 10000), 
      new Employee("Jessica", 23, 4000), new Employee("Pearl", 33, 6000)};
    
    employeesSorted = new Employee[] {
      new Employee("Earl", 43, 10000), new Employee("Frank", 33, 70000),
      new Employee("Jessica", 23, 4000), new Employee("John", 23, 5000), 
      new Employee("Pearl", 33, 4000), new Employee("Steve", 26, 6000)};
    
    employeesSortedByAge = new Employee[] { 
      new Employee("John", 23, 5000), new Employee("Jessica", 23, 4000), 
      new Employee("Steve", 26, 6000), new Employee("Frank", 33, 70000), 
      new Employee("Pearl", 33, 4000), new Employee("Earl", 43, 10000)};
}

我们也可以对数组或自定义对象的集合进行排序。

  1. 按照自然顺序（使用Comparable接口）或
  2. 按照Comparator接口提供的顺序进行

6.1.使用Comparable

java中的自然顺序是指在一个给定的数组或集合中，基元或对象应该被有序地排序的一个顺序。

java.util.Arrays 和java.util.Collections 都有一个sort()方法，强烈建议自然顺序应与equals的语义相一致。

在这个例子中，我们将把具有相同name的员工视为平等的。

@Test
public void givenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder() {
    Arrays.sort(employees);

    assertTrue(Arrays.equals(employees, employeesSorted));
}

你可以通过实现一个Comparable 接口来定义元素的自然顺序，该接口有compareTo()方法，用于比较当前对象和作为参数传递的对象。

为了清楚地理解这一点，让我们看看一个实现了Comparable Interface的Employee类的例子。

public class Employee implements Comparable {
    ...

    @Override
    public boolean equals(Object obj) {
        return ((Employee) obj).getName().equals(getName());
    }

    @Override
    public int compareTo(Object o) {
        Employee e = (Employee) o;
        return getName().compareTo(e.getName());
    }
}

一般来说，比较的逻辑将被写入方法compareTo。这里我们要比较雇员的顺序或雇员字段的name。如果两个雇员有相同的名字，他们将是相等的。

现在，当Arrays.sort(employees);在上述代码中被调用时，我们现在知道了根据name对雇员进行排序的逻辑和顺序。

[("Earl", 43, 10000),("Frank", 33, 70000), ("Jessica", 23, 4000),
 ("John", 23, 5000),("Pearl", 33, 4000), ("Steve", 26, 6000)]

我们可以看到数组是按雇员的名字排序的 – 这现在成为Employee类的自然顺序。

6.2.使用Comparator

现在，让我们使用Comparator接口实现对元素进行排序 – 在这里，我们将匿名的内部类即时传递给Arrays.sort()API。

@Test
public void givenIntegerArray_whenUsingSort_thenSortedArray() {
    Integer [] integers = ArrayUtils.toObject(toSort);
    Arrays.sort(integers, new Comparator<Integer>() {
        @Override
        public int compare(Integer a, Integer b) {
            return Integer.compare(a, b);
        }
    });
 
    assertTrue(Arrays.equals(integers, ArrayUtils.toObject(sortedInts)));
}

现在让我们根据salary – 对雇员进行排序，并传入另一个比较器的实现。

Arrays.sort(employees, new Comparator<Employee>() {
    @Override
    public int compare(Employee o1, Employee o2) {
       return Double.compare(o1.getSalary(), o2.getSalary());
    }
 });

基于salary的排序的Employees数组将是：

[(Jessica,23,4000.0), (John,23,5000.0), (Pearl,33,6000.0), (Steve,26,6000.0), 
(Frank,33,7000.0), (Earl,43,10000.0)]

注意，我们可以用Collections.sort()以类似的方式对List和Set的对象按自然或自定义顺序进行排序，就像上面对数组所描述的那样。

7.用Lambdas进行排序

从Java 8开始，我们可以使用Lambdas来实现Comparator功能接口。

您可以看看Java 8中的Lambdas写的内容，以了解语法。

让我们替换掉旧的比较器吧：

Comparator<Integer> c  = new Comparator<>() {
    @Override
    public int compare(Integer a, Integer b) {
        return Integer.compare(a, b);
    }
}

与之等价的实现，使用Lambda表达式：

Comparator<Integer> c = (a, b) -> Integer.compare(a, b);

最后，我们来写一下测试：

@Test
public void givenArray_whenUsingSortWithLambdas_thenSortedArray() {
    Integer [] integersToSort = ArrayUtils.toObject(toSort);
    Arrays.sort(integersToSort, (a, b) -> {
        return Integer.compare(a, b);
    });
 
    assertTrue(Arrays.equals(integersToSort, 
      ArrayUtils.toObject(sortedInts)));
}

正如你所看到的，这里的逻辑更干净、更简明。

8.使用Comparator.comparing和Comparator.thenComparing

Java 8 带有两个对排序有用的新 API – Comparator接口中的comparing() 和thenComparing() 。

这些对于链接Comparator的多个条件非常方便。

让我们考虑这样一种情况：我们可能想通过员工与年龄进行比较，然后再通过姓名进行比较。

@Test
public void givenArrayObjects_whenUsingComparing_thenSortedArrayObjects() {
    List<Employee> employeesList = Arrays.asList(employees);
    employees.sort(Comparator.comparing(Employee::getAge));

    assertTrue(Arrays.toString(employees.toArray())
      .equals(sortedArrayString));
}

在这个例子中，Employee::getAge是Comparator接口的排序键，实现了一个具有比较功能的接口。

下面是排序后的Employees数组。

[(John,23,5000.0), (Jessica,23,4000.0), (Steve,26,6000.0), (Frank,33,7000.0), 
(Pearl,33,6000.0), (Earl,43,10000.0)]

这里的雇员是根据年龄来排序的。

我们可以看到John和Jessica年龄相同–；这意味着现在的顺序逻辑应该考虑到他们的名字--我们可以用thenComparing()来实现。

... 
employees.sort(Comparator.comparing(Employee::getAge)
  .thenComparing(Employee::getName)); 
...

用上述代码片段进行排序后，雇员数组中的元素将被排序为：

[(Jessica,23,4000.0), 
 (John,23,5000.0), 
 (Steve,26,6000.0), 
 (Frank,33,7000.0), 
 (Pearl,33,6000.0), 
 (Earl,43,10000.0)
]

因此 comparing() 和thenComparing()肯定会使更复杂的排序场景的实现变得更干净。

9.结语

在这篇文章中，我们看到了如何将排序应用于Array、List、Set和Map。

我们还看到了关于Java 8的功能如何在排序中发挥作用的简要介绍，如Lambdas的使用、comparing()和thenComparing()以及parallelSort()等。

文章中使用的所有例子都可以在GitHub上找到。

最后更新2023-03-20
0 个评论
标签
Sorting