Java 中的排序

原文：https://www.studytonight.com/java-examples/sorting-in-java

排序是一种非常常见的操作，Java 提供了不同的内置方法，可以用来对不同的数据结构进行排序。本教程将解释如何在 Java 中对数组、集合和用户定义的类实例进行排序。

Java 中的数组排序

数组是一种简单的数据结构，用于以有序的方式存储相似类型的数据。Arrays 类的 sort() 方法可用于对整个数组或数组的一部分进行排序。在内部，该方法使用双轴快速排序算法对原始数据类型进行排序。对于对象数组，它使用归并排序算法。

public static void main(String[] args)
{
    int[] arrToSort = {7, 9, 1, 0, 2, 5, 6, 11};
    System.out.println("Array Before Sorting: " + Arrays.toString(arrToSort));
    Arrays.sort(arrToSort);
    System.out.println("Array After Sorting: " + Arrays.toString(arrToSort));
}

排序前的数组:[7，9，1，0，2，5，6，11] 排序后的数组:[0，1，2，5，6，7，9，11]

我们可以向 Arrays.sort()方法传递一个开始索引和一个结束索引，只对数组的一部分进行排序。由索引定义的范围是排他的(不包括结束索引元素)。

public static void main(String[] args)
{
    //Sorting the left half of an Array
    int[] arrToSort = {7, 9, 1, 0, 2, 6, 11, 5, -1, 20};
    System.out.println("Array Before Sorting: " + Arrays.toString(arrToSort));
    int from = 0;
    int to = arrToSort.length / 2;
    Arrays.sort(arrToSort, from, to);
    System.out.println("Array After Sorting: " + Arrays.toString(arrToSort));
}

排序前的数组:[7，9，1，0，2，6，11，5，-1，20] 排序后的数组:[0，1，2，7，9，6，11，5，-1，20]

Java 8 有一个新的parallels art()方法，使用多线程来同时对数组的不同部分进行排序。这种方法首先将数组分成较小的数组，然后不同的线程对这些较小的数组进行并行排序。然后它们被合并回一个单独的排序数组。就像 Arrays.sort()方法一样，我们可以使用 parallelSort()对数组的一部分进行排序。

public static void main(String[] args)
{
    //Sorting using parallel sort
    int[] arrToSort = {7, 9, 1, 0, 2, 5, 6, 11};
    System.out.println("Array Before Sorting: " + Arrays.toString(arrToSort));
    Arrays.parallelSort(arrToSort);
    System.out.println("Array After Sorting: " + Arrays.toString(arrToSort));
}

排序前的数组:[7，9，1，0，2，5，6，11] 排序后的数组:[0，1，2，5，6，7，9，11]

在 Java 中对集合进行排序

Java 中的 Collections 框架提供了多种数据结构来存储和操作数据。列表、集合和映射是最常用的集合。在本节中，我们将学习如何对这些集合进行排序。

排序列表

集合框架提供了一种对列表进行排序的 Collections.sort() 方法。该方法还可以将Comparator作为参数，并相应地对列表进行排序。

public static void main(String[] args)
{
    //Sorting Lists
    List<Integer> listToSort = new ArrayList<Integer>();
    listToSort.add(7);
    listToSort.add(9);
    listToSort.add(0);
    listToSort.add(1);
    listToSort.add(-1);
    System.out.println("List Before Sorting: " + listToSort);

    Collections.sort(listToSort);
    System.out.println("List After Sorting: " + listToSort);
}

排序前列表:[7，9，0，1，-1] 排序后列表:[-1，0，1，7，9]

我们可以使用collections . reverse order()方法对列表进行降序排序。这个方法返回一个Comparator对象，我们可以将其传递给 Collections.sort()方法。

public static void main(String[] args)
{
    //Sorting lists in reverse order
    List<Integer> listToSort = new ArrayList<Integer>();
    listToSort.add(7);
    listToSort.add(9);
    listToSort.add(0);
    listToSort.add(1);
    listToSort.add(-1);
    System.out.println("List Before Sorting: " + listToSort);

    Collections.sort(listToSort, Collections.reverseOrder());
    System.out.println("List After Sorting in descending order: " + listToSort);
}

排序前列表:[7，9，0，1，-1] 排序后列表按降序排列:[9，7，1，0，-1]

排序集

集合用于存储无重复的无序数据。与列表不同，我们没有为集合定义 sort()方法。HashSet 类不维护插入顺序，所以我们不能直接排序。但是我们可以通过将Hashtable的所有元素转移到一个列表中，然后对列表进行排序来查看排序后的值。

public static void main(String[] args)
{
    //Sorting Sets using lists
    HashSet<Integer> setToSort = new HashSet<Integer>();
    setToSort.add(7);
    setToSort.add(9);
    setToSort.add(0);
    setToSort.add(1);
    setToSort.add(-1);
    System.out.println("Set Before Sorting: " + setToSort);

    ArrayList<Integer> listOfSet = new ArrayList<Integer>(setToSort);
    Collections.sort(listOfSet);
    System.out.println("Sorted Values of the Set: " + listOfSet);
}

排序前设置:[0，-1，1，7，9] 集合的排序值:[-1，0，1，7，9]

同样的方法也可以用于 LinkedHashSet。LinkedHashSet 维护元素的插入顺序，排序后的值可以存储回其中。

public static void main(String[] args)
{
    //Sorting Sets using lists
    LinkedHashSet<Integer> setToSort = new LinkedHashSet<Integer>();
    setToSort.add(7);
    setToSort.add(9);
    setToSort.add(0);
    setToSort.add(1);
    setToSort.add(-1);
    System.out.println("Set Before Sorting: " + setToSort);

    ArrayList<Integer> listOfSet = new ArrayList<Integer>(setToSort);
    Collections.sort(listOfSet);

    //Transferring sorted values to the set
    setToSort = new LinkedHashSet<Integer>(); 
    for(Integer i : listOfSet)
    {
        setToSort.add(i);
    }

    System.out.println("Set After Sorting: " + setToSort);
}

排序前设置:【7，9，0，1，-1】 排序后设置:【-1，0，1，7，9】

TreeSet 按排序顺序存储元素。因此，我们可以将一个 HashSet 或 LinkedHashSet 转换为一个 TreeSet，并查看排序后的值。

public static void main(String[] args)
{
    //Sorting Sets using TreeSets
    HashSet<Integer> setToSort = new HashSet<Integer>();
    setToSort.add(7);
    setToSort.add(9);
    setToSort.add(0);
    setToSort.add(1);
    setToSort.add(-1);
    System.out.println("Set Before Sorting: " + setToSort);

    TreeSet<Integer> sortedSet = new TreeSet<Integer>(setToSort);
    System.out.println("Set After Sorting: " + sortedSet);
}

排序前设置:[0，-1，1，7，9] 排序后设置:[-1，0，1，7，9]

SortedMap

映射用于存储一系列键值对。就像集合一样，我们没有任何内置的映射排序()方法。我们可以根据关键字或值对映射进行排序。让我们学习如何按键和值对映射进行排序。

按关键字对映射进行排序

HashMaps 和 HashSets 一样，不维护插入顺序。我们仍然可以在列表的帮助下查看排序后的数据。我们将把Hashtable的键转移到一个ArrayList中，然后我们将对这个列表进行排序。我们可以通过使用映射的 get() 方法来获取排序关键字的值。

public static void main(String[] args)
{
    //Sorting Map by Keys using Lists
    HashMap<Integer, String> mapToSort = new HashMap<Integer, String>();
    mapToSort.put(3, "Jessica");
    mapToSort.put(112, "Victor");
    mapToSort.put(15, "Harry");
    mapToSort.put(104, "Simon");
    mapToSort.put(21, "Justin");
    System.out.println("Map before sorting: ");
    for(Map.Entry<Integer, String> e : mapToSort.entrySet())
        System.out.println(e.getKey() + " " + e.getValue());

    ArrayList<Integer> sortedKeys = new ArrayList<Integer>(mapToSort.keySet());
    Collections.sort(sortedKeys);

    System.out.println("\nMap After sorting: ");
    for(Integer i : sortedKeys)
        System.out.println(i + " " + mapToSort.get(i));
}

排序前映射: 112 维克多 3 杰西卡 21 贾斯汀 104 西蒙 15 哈利 T7】排序后映射: 3 杰西卡 15 哈利 21 贾斯汀 104 西蒙 112 维克多

我们还可以创建一个新的 LinkedHashMap，并将排序后的键和相应的值添加到其中。LinkedHashMap 维护插入顺序。

public static void main(String[] args)
{
    HashMap<Integer, String> mapToSort = new HashMap<Integer, String>();
    mapToSort.put(3, "Jessica");
    mapToSort.put(112, "Victor");
    mapToSort.put(15, "Harry");
    mapToSort.put(104, "Simon");
    mapToSort.put(21, "Justin");
    System.out.println("Map before sorting: ");
    for(Map.Entry<Integer, String> e : mapToSort.entrySet())
        System.out.println(e.getKey() + " " + e.getValue());

    ArrayList<Integer> sortedKeys = new ArrayList<Integer>(mapToSort.keySet());
    Collections.sort(sortedKeys);

    //Creating a new LinkedHashMap
    LinkedHashMap<Integer, String> sortedMap = new LinkedHashMap<Integer, String>();
    for(Integer i : sortedKeys)
        sortedMap.put(i, mapToSort.get(i));

    System.out.println("\nThe Sorted Map is:");
    for(Map.Entry<Integer, String> e : sortedMap.entrySet())
        System.out.println(e.getKey() + " " + e.getValue());
}

排序前的映射: 112 维克多 3 杰西卡 21 贾斯汀 104 西蒙 15 哈利 T7【排序后的映射是: 3 杰西卡 15 哈利 21 贾斯汀 104 西蒙 112 维克多

另一种按键排序映射的简单方法是使用树形映射。默认情况下，TreeMap按排序顺序存储键值对。

public static void main(String[] args)
{
    //Sorting Map by Keys using TreeMap
    HashMap<Integer, String> mapToSort = new HashMap<Integer, String>();
    mapToSort.put(3, "Jessica");
    mapToSort.put(112, "Victor");
    mapToSort.put(15, "Harry");
    mapToSort.put(104, "Simon");
    mapToSort.put(21, "Justin");

    System.out.println("Map before sorting: ");
    for(Map.Entry<Integer, String> e : mapToSort.entrySet())
        System.out.println(e.getKey() + " " + e.getValue());

    TreeMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
    sortedMap.putAll(mapToSort);

    System.out.println("\nSorted TreeMap: ");
    for(Map.Entry<Integer, String> e : sortedMap.entrySet())
        System.out.println(e.getKey() + " " + e.getValue());
}

排序前的映射: 112 维克多 3 杰西卡 21 贾斯汀 104 西蒙 15 哈利 T7】排序后的树形映射: 3 杰西卡 15 哈利 21 贾斯汀 104 西蒙 112 维克多

按值排序映射

根据值对映射进行排序有点困难。我们将创建一个实现Comparator接口的类。接下来，我们将在其中定义一个 compare()方法。这个类的代码如下所示。

class CompareMapValue implements Comparator<Map.Entry<Integer, String>>
{
    @Override
    public int compare(Entry<Integer, String> o1, Entry<Integer, String> o2)
    {
        String val1 = o1.getValue();
        String val2 = o2.getValue();
        return val1.compareTo(val2);
    }
}

接下来，我们将创建一个包含所有键值对的ArrayList，并使用 Collections.sort()方法对它们进行排序。我们将把先前定义的类的一个对象传递给 sort()方法。我们还可以使用 LinkedHashMap 来存储排序后的值。在我们的代码中，我们刚刚打印了排序后的值。

public static void main(String[] args)
{

    //Sorting map by values
    HashMap<Integer, String> mapToSort = new HashMap<Integer, String>();
    mapToSort.put(3, "Jessica");
    mapToSort.put(112, "Victor");
    mapToSort.put(15, "Harry");
    mapToSort.put(104, "Simon");
    mapToSort.put(21, "Justin");

    System.out.println("Map before sorting: ");
    for(Map.Entry<Integer, String> e : mapToSort.entrySet())
        System.out.println(e.getKey() + " " + e.getValue());

    ArrayList<Map.Entry<Integer, String>> list = new ArrayList<>(mapToSort.entrySet());
    CompareMapValue c = new CompareMapValue();
    Collections.sort(list, c);

    System.out.println("\nSorted Values: ");
    for (Map.Entry<Integer, String> e : list)
    {
        System.out.println(e.getKey() + " " + e.getValue());
    }
}

排序前的映射: 112 维克多 3 杰西卡 21 贾斯汀 104 西蒙 15 哈利 T7】排序后的值: 15 哈利 3 杰西卡 21 贾斯汀 104 西蒙 112 维克多

对用户定义的类对象进行排序

我们可以通过使用 Comparable 和 Comparator 接口对用户定义的类对象进行排序。请参考我们关于Comparator和Comparator的文章，了解如何使用它们。

要使用Comparator，我们需要创建一个单独的类，但是 Java 8 为我们提供了 Lambda 表达式，可以用来更有效地实现Comparator。假设我们需要以相反的顺序对整数数组进行排序。我们可以创建一个实现 Comparator 接口并覆盖 compare()方法的类，如下所示。

class CompareReverse implements Comparator<Integer>
{
    @Override
    public int compare(Integer o1, Integer o2) {
        return -o1.compareTo(o2);
    }
}

或者我们可以编写下面的 Lambda 表达式来做同样的事情。

Comparator<Integer> c = (x, y) -> -(Integer.compare(x, y));

两者给出的输出是一样的。

public static void main(String[] args)
{
    Integer[] arr = {4, 9, 1, -1, 0, 5};
    List<Integer> arrList1 = Arrays.asList(arr);
    List<Integer> arrList2 = Arrays.asList(arr);

    CompareReverse c1 = new CompareReverse();
    Comparator<Integer> c2 = (x, y) -> -(Integer.compare(x, y));

    Collections.sort(arrList1, c1);
    Collections.sort(arrList2, c2);

    System.out.println(arrList1);
    System.out.println(arrList2);
}

【9，5，4，1，0，-1】 【9，5，4，1，0，-1】

使用比较()和比较()方法

comparing()和 then comparison()方法也是使用Comparator对用户定义的类实例进行排序的好方法。考虑一个以姓名和平均绩点为属性的学生班级。

class Student
{
    String name;
    Double gpa;

    Student(String name, Double gpa)
    {
        this.name = name;
        this.gpa = gpa;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Double getGpa() {
        return gpa;
    }

    public void setGpa(Double gpa) {
        this.gpa = gpa;
    }
}

如果我们希望根据学生的平均成绩对他们进行排序，那么我们可以使用 comparing()方法，如下所示。

public static void main(String[] args)
{
    ArrayList<Student> listOfStudents = new ArrayList<Student>();
    listOfStudents.add(new Student("Rachel", 8.08));
    listOfStudents.add(new Student("Justin", 8.08));
    listOfStudents.add(new Student("Clay", 9.75));
    listOfStudents.add(new Student("Austin", 9.75));
    listOfStudents.add(new Student("Chloe", 9.33));
    Comparator<Student> c = Comparator.comparing(Student :: getGpa);

    Collections.sort(listOfStudents, c);

    for(Student s : listOfStudents)
        System.out.println(s.getName() + " " + s.getGpa());
}

瑞秋 8.08 贾斯汀 8.08 克洛伊 9.33 克莱 9.75 奥斯汀 9.75

让我们先按学生姓名，然后按学生的 GPA 对上面的数组进行排序。我们可以使用 then comparing()方法和 comparising()方法来实现这一点。这个场景的代码如下所示。确保定义适当的吸气剂与这些方法一起使用。

public static void main(String[] args)
{
    ArrayList<Student> listOfStudents = new ArrayList<Student>();
    listOfStudents.add(new Student("Rachel", 8.08));
    listOfStudents.add(new Student("Justin", 8.08));
    listOfStudents.add(new Student("Clay", 9.75));
    listOfStudents.add(new Student("Austin", 9.75));
    listOfStudents.add(new Student("Chloe", 9.33));
    Comparator<Student> c = Comparator.comparing(Student :: getGpa).thenComparing(Student :: getName);

    Collections.sort(listOfStudents, c);

    for(Student s : listOfStudents)
        System.out.println(s.getName() + " " + s.getGpa());
}

贾斯汀 8.08 瑞秋 8.08 克洛伊 9.33 奥斯汀 9.75 克莱 9.75

摘要

本教程解释了如何在 Java 中对不同的数据结构(如数组、列表、集合和映射)进行排序。可以使用 Arrays.sort()方法对数组进行排序。如果我们有一个更大的数组，那么建议使用 parallelSort()，因为它比普通的 Sort()方法更有效。集合框架为列表接口提供了一个 sort()方法。我们还可以使用列表对集合和映射进行排序。TreeSet 也可以用来按排序顺序存储值。同样，TreeMap也可以用来对映射进行排序。