MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

Java Collections工具类对集合的排序和查找操作

2022-03-202.9k 阅读

Java Collections工具类对集合的排序操作

集合排序的重要性

在Java编程中，处理集合数据时，对其进行排序是一项极为常见且重要的操作。排序后的集合不仅便于数据的查找和处理，还能使数据呈现出更有组织的结构。例如，在一个存储学生成绩的集合中，按成绩从高到低排序后，我们可以轻松确定成绩排名靠前的学生，为成绩分析等后续操作提供便利。

Collections工具类中的排序方法概述

Java的java.util.Collections工具类提供了丰富的方法来对集合进行排序。其中最常用的是sort(List<T> list)和sort(List<T> list, Comparator<? super T> c)方法。

使用sort(List<T> list)方法进行自然排序

当集合中的元素实现了Comparable接口时，我们可以使用sort(List<T> list)方法对集合进行自然排序。Comparable接口定义了一个compareTo方法，该方法定义了元素之间的自然顺序。

以下是一个简单的示例，展示如何对List<Integer>进行自然排序：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class NaturalSortExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(5);
        numbers.add(2);
        numbers.add(8);
        numbers.add(1);

        Collections.sort(numbers);

        System.out.println("Sorted list: " + numbers);
    }
}

在上述代码中，Integer类已经实现了Comparable接口，因此可以直接使用Collections.sort(numbers)方法对numbers列表进行自然排序。运行程序后，输出结果为Sorted list: [1, 2, 5, 8]，表明列表已按升序排列。

自定义排序规则：使用sort(List<T> list, Comparator<? super T> c)方法

当集合中的元素没有实现Comparable接口，或者我们希望使用不同于自然顺序的排序规则时，可以使用sort(List<T> list, Comparator<? super T> c)方法。Comparator接口定义了一个compare方法，用于定义两个元素之间的比较逻辑。

假设有一个自定义的Person类，包含name和age属性，我们希望按年龄对Person对象的列表进行排序。示例代码如下：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

class AgeComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        return p1.getAge() - p2.getAge();
    }
}

public class CustomSortExample {
    public static void main(String[] args) {
        List<Person> people = new ArrayList<>();
        people.add(new Person("Alice", 25));
        people.add(new Person("Bob", 20));
        people.add(new Person("Charlie", 30));

        Collections.sort(people, new AgeComparator());

        System.out.println("Sorted list by age: " + people);
    }
}

在上述代码中，我们定义了一个AgeComparator类实现了Comparator接口，并在compare方法中定义了按年龄比较的逻辑。然后，使用Collections.sort(people, new AgeComparator())方法对people列表按年龄进行排序。运行程序后，输出结果为Sorted list by age: [Person{name='Bob', age=20}, Person{name='Alice', age=25}, Person{name='Charlie', age=30}]，表明列表已按年龄升序排列。

降序排序

如果要进行降序排序，可以在Comparator中调整比较逻辑。例如，对于上述Person类按年龄降序排序，修改AgeComparator如下：

class AgeDescendingComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        return p2.getAge() - p1.getAge();
    }
}

然后在main方法中使用新的比较器：

Collections.sort(people, new AgeDescendingComparator());
System.out.println("Sorted list by age in descending order: " + people);

运行后，输出结果为Sorted list by age in descending order: [Person{name='Charlie', age=30}, Person{name='Alice', age=25}, Person{name='Bob', age=20}]，实现了按年龄降序排序。

对复杂对象进行多字段排序

在实际应用中，可能需要对包含多个字段的复杂对象进行排序。例如，对于Person类，先按年龄排序，如果年龄相同，再按名字的字母顺序排序。示例代码如下：

class MultiFieldComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        int ageComparison = p1.getAge() - p2.getAge();
        if (ageComparison != 0) {
            return ageComparison;
        } else {
            return p1.getName().compareTo(p2.getName());
        }
    }
}

在main方法中使用该比较器：

Collections.sort(people, new MultiFieldComparator());
System.out.println("Sorted list by age and then name: " + people);

假设people列表中有两个年龄相同的人，运行程序后，列表将先按年龄排序，年龄相同的人再按名字的字母顺序排序。

对Set集合进行排序

Set集合本身是无序的，但我们可以将其转换为List，然后进行排序。例如，对于HashSet：

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SortSetExample {
    public static void main(String[] args) {
        Set<Integer> numbersSet = new HashSet<>();
        numbersSet.add(5);
        numbersSet.add(2);
        numbersSet.add(8);
        numbersSet.add(1);

        List<Integer> numbersList = new ArrayList<>(numbersSet);
        Collections.sort(numbersList);

        System.out.println("Sorted list from set: " + numbersList);
    }
}

在上述代码中，先将HashSet转换为ArrayList，然后对ArrayList进行排序，从而实现对Set集合元素的排序。

对Map集合进行排序

Map集合本身也是无序的。如果要对Map按键或值进行排序，可以先将Map的键或值转换为List，然后进行排序。例如，按Map的键进行排序：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class SortMapByKeyExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("banana", 3);
        map.put("apple", 2);
        map.put("cherry", 1);

        List<String> keys = new ArrayList<>(map.keySet());
        Collections.sort(keys);

        Map<String, Integer> sortedMap = new LinkedHashMap<>();
        for (String key : keys) {
            sortedMap.put(key, map.get(key));
        }

        System.out.println("Sorted map by key: " + sortedMap);
    }
}

在上述代码中，先将Map的键转换为List并排序，然后创建一个新的LinkedHashMap，按照排序后的键顺序将键值对放入新的Map中，从而实现按键排序的Map。

如果要按值排序，可以如下操作：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class SortMapByValueExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("banana", 3);
        map.put("apple", 2);
        map.put("cherry", 1);

        List<Entry<String, Integer>> entries = new ArrayList<>(map.entrySet());
        Collections.sort(entries, new Comparator<Entry<String, Integer>>() {
            @Override
            public int compare(Entry<String, Integer> e1, Entry<String, Integer> e2) {
                return e1.getValue() - e2.getValue();
            }
        });

        Map<String, Integer> sortedMap = new LinkedHashMap<>();
        for (Entry<String, Integer> entry : entries) {
            sortedMap.put(entry.getKey(), entry.getValue());
        }

        System.out.println("Sorted map by value: " + sortedMap);
    }
}

在上述代码中，先将Map的entrySet转换为List，然后使用Comparator按值进行排序，最后将排序后的entry放入新的LinkedHashMap中，实现按值排序的Map。

Java Collections工具类对集合的查找操作

查找操作的意义

在处理集合数据时，查找特定元素或元素的位置是非常常见的需求。例如，在一个存储用户信息的集合中，查找某个特定用户的信息，或者查找某个特定值在集合中的索引位置等。

使用binarySearch(List<? extends Comparable<? super T>> list, T key)方法进行二分查找

二分查找是一种高效的查找算法，前提是集合必须是有序的。Collections工具类的binarySearch(List<? extends Comparable<? super T>> list, T key)方法用于在有序列表中查找指定的元素。如果找到元素，返回其索引；如果未找到，返回一个负数，该负数是插入点（即如果将键插入列表中，应该插入的位置）的负值减1。

以下是一个对List<Integer>进行二分查找的示例：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BinarySearchExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(1);
        numbers.add(3);
        numbers.add(5);
        numbers.add(7);

        int key = 5;
        int result = Collections.binarySearch(numbers, key);

        if (result >= 0) {
            System.out.println("Element " + key + " found at index " + result);
        } else {
            System.out.println("Element " + key + " not found. Insertion point: " + (-result - 1));
        }
    }
}

在上述代码中，numbers列表是有序的，通过Collections.binarySearch(numbers, key)方法查找值为5的元素。由于找到了该元素，输出结果为Element 5 found at index 2。

使用binarySearch(List<? extends T> list, T key, Comparator<? super T> c)方法进行二分查找

当集合中的元素没有实现Comparable接口，或者需要使用自定义的比较逻辑进行二分查找时，可以使用binarySearch(List<? extends T> list, T key, Comparator<? super T> c)方法。

假设有一个Person类，我们希望在按年龄排序的Person列表中查找特定年龄的人，示例代码如下：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public int getAge() {
        return age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

class AgeComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        return p1.getAge() - p2.getAge();
    }
}

public class CustomBinarySearchExample {
    public static void main(String[] args) {
        List<Person> people = new ArrayList<>();
        people.add(new Person("Alice", 20));
        people.add(new Person("Bob", 25));
        people.add(new Person("Charlie", 30));

        int targetAge = 25;
        Person targetPerson = new Person("", targetAge);
        int result = Collections.binarySearch(people, targetPerson, new AgeComparator());

        if (result >= 0) {
            System.out.println("Person with age " + targetAge + " found at index " + result);
        } else {
            System.out.println("Person with age " + targetAge + " not found. Insertion point: " + (-result - 1));
        }
    }
}

在上述代码中，我们定义了AgeComparator来按年龄比较Person对象。通过Collections.binarySearch(people, targetPerson, new AgeComparator())方法在people列表中查找年龄为25的Person对象。如果找到，输出其索引；否则，输出插入点。

使用indexOfSubList(List<?> source, List<?> target)方法查找子列表

Collections工具类的indexOfSubList(List<?> source, List<?> target)方法用于在源列表中查找目标子列表的起始索引。如果找到，返回子列表在源列表中第一次出现的起始索引；如果未找到，返回 -1。

以下是一个示例：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class IndexOfSubListExample {
    public static void main(String[] args) {
        List<Integer> source = new ArrayList<>();
        source.add(1);
        source.add(2);
        source.add(3);
        source.add(4);
        source.add(5);

        List<Integer> target = new ArrayList<>();
        target.add(3);
        target.add(4);

        int result = Collections.indexOfSubList(source, target);

        if (result >= 0) {
            System.out.println("Sub - list found at index " + result);
        } else {
            System.out.println("Sub - list not found");
        }
    }
}

在上述代码中，source列表为[1, 2, 3, 4, 5]，target子列表为[3, 4]。通过Collections.indexOfSubList(source, target)方法查找子列表，由于找到，输出结果为Sub - list found at index 2。

使用lastIndexOfSubList(List<?> source, List<?> target)方法查找子列表最后一次出现的位置

lastIndexOfSubList(List<?> source, List<?> target)方法用于在源列表中查找目标子列表最后一次出现的起始索引。如果找到，返回子列表在源列表中最后一次出现的起始索引；如果未找到，返回 -1。

示例代码如下：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LastIndexOfSubListExample {
    public static void main(String[] args) {
        List<Integer> source = new ArrayList<>();
        source.add(1);
        source.add(2);
        source.add(3);
        source.add(4);
        source.add(3);
        source.add(4);

        List<Integer> target = new ArrayList<>();
        target.add(3);
        target.add(4);

        int result = Collections.lastIndexOfSubList(source, target);

        if (result >= 0) {
            System.out.println("Sub - list found at last index " + result);
        } else {
            System.out.println("Sub - list not found");
        }
    }
}

在上述代码中，source列表包含两次[3, 4]子列表，通过Collections.lastIndexOfSubList(source, target)方法查找子列表最后一次出现的位置，输出结果为Sub - list found at last index 4。

使用frequency(Collection<?> c, Object o)方法统计元素出现的频率

Collections工具类的frequency(Collection<?> c, Object o)方法用于统计指定元素在集合中出现的次数。

以下是一个示例：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class FrequencyExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(1);
        numbers.add(2);
        numbers.add(2);
        numbers.add(3);
        numbers.add(2);

        int count = Collections.frequency(numbers, 2);
        System.out.println("The number of 2s in the list is: " + count);
    }
}

在上述代码中，通过Collections.frequency(numbers, 2)方法统计numbers列表中元素2出现的次数，输出结果为The number of 2s in the list is: 3。

使用disjoint(Collection<?> c1, Collection<?> c2)方法判断两个集合是否不相交

Collections工具类的disjoint(Collection<?> c1, Collection<?> c2)方法用于判断两个集合是否没有共同的元素。如果两个集合没有共同元素，返回true；否则，返回false。

示例代码如下：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class DisjointExample {
    public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);

        List<Integer> list2 = new ArrayList<>();
        list2.add(4);
        list2.add(5);
        list2.add(6);

        boolean result = Collections.disjoint(list1, list2);
        System.out.println("Are the two lists disjoint? " + result);

        List<Integer> list3 = new ArrayList<>();
        list3.add(3);
        list3.add(4);
        list3.add(5);

        boolean result2 = Collections.disjoint(list1, list3);
        System.out.println("Are list1 and list3 disjoint? " + result2);
    }
}

在上述代码中，list1和list2没有共同元素，Collections.disjoint(list1, list2)返回true；list1和list3有共同元素3，Collections.disjoint(list1, list3)返回false。

通过对Java Collections工具类中排序和查找操作的深入了解和实践，我们能够更加高效地处理集合数据，提升程序的性能和功能。无论是简单的数值集合，还是复杂的自定义对象集合，这些方法都为我们提供了强大的工具来满足各种数据处理需求。在实际开发中，根据具体的业务场景选择合适的排序和查找方法，能够使代码更加简洁、高效且易于维护。