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

Kotlin集合排序与分组

2023-09-195.3k 阅读

Kotlin 集合排序

在 Kotlin 编程中，集合排序是一项常见且重要的操作。集合排序可以帮助我们以特定的顺序组织数据，便于查找、分析和处理。Kotlin 提供了丰富的方法来对集合进行排序，无论是简单的列表还是复杂的自定义对象集合。

基本类型集合的排序

Kotlin 对基本类型的集合排序非常直观。例如，对于一个 List<Int>，我们可以使用 sorted() 函数对其进行升序排序。

fun main() {
    val numbers = listOf(5, 2, 8, 1, 9)
    val sortedNumbers = numbers.sorted()
    println(sortedNumbers)
}

上述代码中，numbers 是一个包含整数的列表，通过调用 sorted() 函数，我们得到了一个新的升序排列的列表 sortedNumbers，并将其打印出来。输出结果为 [1, 2, 5, 8, 9]。

如果我们想要降序排序，可以使用 sortedDescending() 函数。

fun main() {
    val numbers = listOf(5, 2, 8, 1, 9)
    val sortedNumbers = numbers.sortedDescending()
    println(sortedNumbers)
}

这段代码中，sortedDescending() 函数将 numbers 列表按降序排列，输出结果为 [9, 8, 5, 2, 1]。

自定义对象集合的排序

当处理自定义对象的集合时，排序就稍微复杂一些，因为 Kotlin 需要知道如何比较这些对象。我们需要为自定义对象提供一种比较的方式。有两种常见的方法来实现这一点：实现 Comparable 接口和使用比较器（Comparator）。

实现 Comparable 接口

假设我们有一个表示人员的类 Person，我们想要根据年龄对人员列表进行排序。

data class Person(val name: String, val age: Int) : Comparable<Person> {
    override fun compareTo(other: Person): Int {
        return this.age - other.age
    }
}

fun main() {
    val people = listOf(
        Person("Alice", 30),
        Person("Bob", 25),
        Person("Charlie", 35)
    )
    val sortedPeople = people.sorted()
    sortedPeople.forEach { println("Name: ${it.name}, Age: ${it.age}") }
}

在上述代码中，Person 类实现了 Comparable 接口，并在 compareTo 方法中定义了比较逻辑，这里是根据年龄进行比较。然后，我们可以直接对 Person 列表调用 sorted() 函数，它会按照我们定义的比较逻辑进行排序。输出结果为：

Name: Bob, Age: 25
Name: Alice, Age: 30
Name: Charlie, Age: 35

使用比较器（Comparator）

除了实现 Comparable 接口，我们还可以使用 Comparator 来定义比较逻辑。这种方法更加灵活，因为我们可以在需要排序的地方临时定义比较逻辑，而不需要修改类的定义。

data class Person(val name: String, val age: Int)

fun main() {
    val people = listOf(
        Person("Alice", 30),
        Person("Bob", 25),
        Person("Charlie", 35)
    )
    val sortedPeople = people.sortedWith(Comparator { p1, p2 ->
        p1.age - p2.age
    })
    sortedPeople.forEach { println("Name: ${it.name}, Age: ${it.age}") }
}

这里，我们通过 sortedWith 函数并传入一个 Comparator 来对 Person 列表进行排序。Comparator 的 compare 方法定义了比较逻辑，同样是根据年龄比较。这种方式适用于需要在不同地方以不同方式对同一类对象进行排序的场景。

多字段排序

有时候，我们需要根据多个字段对集合进行排序。例如，对于 Person 类，我们可能先按年龄排序，如果年龄相同，再按名字排序。

data class Person(val name: String, val age: Int) : Comparable<Person> {
    override fun compareTo(other: Person): Int {
        val ageComparison = this.age - other.age
        if (ageComparison != 0) {
            return ageComparison
        }
        return this.name.compareTo(other.name)
    }
}

fun main() {
    val people = listOf(
        Person("Alice", 30),
        Person("Bob", 30),
        Person("Charlie", 35)
    )
    val sortedPeople = people.sorted()
    sortedPeople.forEach { println("Name: ${it.name}, Age: ${it.age}") }
}

在上述 Person 类的 compareTo 方法中，首先比较年龄，如果年龄相同，则比较名字。这样就实现了多字段排序。输出结果为：

Name: Alice, Age: 30
Name: Bob, Age: 30
Name: Charlie, Age: 35

Kotlin 集合分组

集合分组是将集合中的元素按照某个属性或规则分成不同的组。这在数据分析、统计等场景中非常有用。Kotlin 提供了 groupBy 函数来实现集合分组。

按单一属性分组

假设我们有一个水果列表，每个水果对象包含名称和颜色属性，我们想按颜色对水果进行分组。

data class Fruit(val name: String, val color: String)

fun main() {
    val fruits = listOf(
        Fruit("Apple", "Red"),
        Fruit("Banana", "Yellow"),
        Fruit("Cherry", "Red"),
        Fruit("Lemon", "Yellow")
    )
    val groupedFruits = fruits.groupBy { it.color }
    groupedFruits.forEach { (color, fruitsInColor) ->
        println("Color: $color")
        fruitsInColor.forEach { println(" - ${it.name}") }
    }
}

在上述代码中，通过 groupBy 函数，我们将 fruits 列表按水果的颜色进行分组。groupBy 函数接受一个 Lambda 表达式，该表达式返回用于分组的属性（这里是颜色）。输出结果为：

Color: Red
 - Apple
 - Cherry
Color: Yellow
 - Banana
 - Lemon

按复杂逻辑分组

除了按简单属性分组，我们还可以根据更复杂的逻辑进行分组。例如，我们可以根据水果名称的长度是否大于 5 来分组。

data class Fruit(val name: String, val color: String)

fun main() {
    val fruits = listOf(
        Fruit("Apple", "Red"),
        Fruit("Banana", "Yellow"),
        Fruit("Cherry", "Red"),
        Fruit("Kiwi", "Brown")
    )
    val groupedFruits = fruits.groupBy { it.name.length > 5 }
    groupedFruits.forEach { (isLongName, fruitsInGroup) ->
        val groupDescription = if (isLongName) "Long names" else "Short names"
        println("Group: $groupDescription")
        fruitsInGroup.forEach { println(" - ${it.name}") }
    }
}

这里，groupBy 函数的 Lambda 表达式返回一个布尔值，表示水果名称长度是否大于 5。根据这个逻辑，水果被分成两组。输出结果为：

Group: Short names
 - Apple
 - Cherry
 - Kiwi
Group: Long names
 - Banana

分组后的统计和处理

分组后，我们通常会对每个组进行一些统计或其他处理。例如，我们可以统计每个颜色组中的水果数量。

data class Fruit(val name: String, val color: String)

fun main() {
    val fruits = listOf(
        Fruit("Apple", "Red"),
        Fruit("Banana", "Yellow"),
        Fruit("Cherry", "Red"),
        Fruit("Lemon", "Yellow")
    )
    val groupedFruits = fruits.groupBy { it.color }
    val fruitCountByColor = groupedFruits.mapValues { it.value.size }
    fruitCountByColor.forEach { (color, count) ->
        println("Color: $color, Fruit count: $count")
    }
}

在上述代码中，我们首先使用 groupBy 函数按颜色分组，然后通过 mapValues 函数将每个组映射为该组中水果的数量。最后，打印出每种颜色的水果数量。输出结果为：

Color: Red, Fruit count: 2
Color: Yellow, Fruit count: 2

多级分组

Kotlin 还支持多级分组，即对已经分组的结果再进行分组。例如，我们可以先按颜色对水果分组，然后在每个颜色组内再按名称长度分组。

data class Fruit(val name: String, val color: String)

fun main() {
    val fruits = listOf(
        Fruit("Apple", "Red"),
        Fruit("Banana", "Yellow"),
        Fruit("Cherry", "Red"),
        Fruit("Kiwi", "Brown")
    )
    val multiLevelGrouped = fruits.groupBy { it.color }.mapValues { colorGroup ->
        colorGroup.value.groupBy { it.name.length > 5 }
    }
    multiLevelGrouped.forEach { (color, lengthGroup) ->
        println("Color: $color")
        lengthGroup.forEach { (isLongName, fruitsInGroup) ->
            val groupDescription = if (isLongName) "Long names" else "Short names"
            println(" - Group: $groupDescription")
            fruitsInGroup.forEach { println(" - - ${it.name}") }
        }
    }
}

在这段代码中，首先按颜色分组，然后对每个颜色组内的水果按名称长度再次分组。输出结果为：

Color: Red
 - Group: Short names
 - - Apple
 - - Cherry
Color: Yellow
 - Group: Long names
 - - Banana
Color: Brown
 - Group: Short names
 - - Kiwi

排序与分组的结合使用

在实际应用中，我们经常需要先对集合进行排序，然后再分组，或者分组后对每个组进行排序。

先排序后分组

假设我们有一个学生列表，每个学生有姓名和成绩属性。我们先按成绩对学生进行排序，然后按成绩的等级（优秀、良好、及格、不及格）分组。

data class Student(val name: String, val score: Int)

fun main() {
    val students = listOf(
        Student("Alice", 85),
        Student("Bob", 60),
        Student("Charlie", 90),
        Student("David", 55)
    )
    val sortedStudents = students.sortedByDescending { it.score }
    val groupedStudents = sortedStudents.groupBy {
        when {
            it.score >= 90 -> "Excellent"
            it.score >= 80 -> "Good"
            it.score >= 60 -> "Pass"
            else -> "Fail"
        }
    }
    groupedStudents.forEach { (grade, studentsInGrade) ->
        println("Grade: $grade")
        studentsInGrade.forEach { println(" - ${it.name}: ${it.score}") }
    }
}

在上述代码中，首先使用 sortedByDescending 函数按成绩降序排序，然后根据成绩范围进行分组。输出结果为：

Grade: Excellent
 - Charlie: 90
Grade: Good
 - Alice: 85
Grade: Pass
 - Bob: 60
Grade: Fail
 - David: 55

分组后排序

我们也可以先分组，然后对每个组内的元素进行排序。例如，对于前面的水果例子，我们先按颜色分组，然后在每个颜色组内按水果名称排序。

data class Fruit(val name: String, val color: String)

fun main() {
    val fruits = listOf(
        Fruit("Apple", "Red"),
        Fruit("Banana", "Yellow"),
        Fruit("Cherry", "Red"),
        Fruit("Lemon", "Yellow")
    )
    val groupedFruits = fruits.groupBy { it.color }
    val sortedGroupedFruits = groupedFruits.mapValues { it.value.sortedBy { it.name } }
    sortedGroupedFruits.forEach { (color, fruitsInColor) ->
        println("Color: $color")
        fruitsInColor.forEach { println(" - ${it.name}") }
    }
}

这里，先按颜色分组，然后通过 mapValues 函数对每个颜色组内的水果按名称排序。输出结果为：

Color: Red
 - Apple
 - Cherry
Color: Yellow
 - Banana
 - Lemon

集合排序与分组的性能考虑

在处理大规模集合时，排序和分组的性能至关重要。

排序的性能

不同的排序算法在时间复杂度和空间复杂度上有所不同。Kotlin 中常用的排序方法（如 sorted 和 sortedDescending）通常使用高效的排序算法，如归并排序或快速排序的变体。这些算法的平均时间复杂度为 O(n log n)，其中 n 是集合的大小。

对于自定义对象的排序，如果实现 Comparable 接口或使用 Comparator 时比较逻辑复杂，可能会影响排序性能。在这种情况下，应尽量简化比较逻辑，避免不必要的计算。

分组的性能

groupBy 函数的时间复杂度取决于集合的大小和分组的属性或逻辑的复杂度。如果分组的逻辑简单（如按单一属性分组），时间复杂度接近 O(n)，其中 n 是集合的大小。但如果分组逻辑复杂，如包含大量的条件判断或复杂的计算，可能会显著增加时间复杂度。

此外，分组操作会创建新的集合结构（通常是 Map）来存储分组结果，这可能会占用较多的内存，特别是在处理大规模集合时。因此，在进行分组操作时，要考虑内存的使用情况。

与 Java 集合排序和分组的对比

Kotlin 与 Java 在集合排序和分组方面有一些差异和优势。

排序

在 Java 中，对基本类型集合排序通常使用 Arrays.sort 方法（对于数组）或 Collections.sort 方法（对于列表）。对于自定义对象，需要实现 Comparable 接口或使用 Comparator，这一点与 Kotlin 类似。

然而，Kotlin 的语法更加简洁。例如，在 Kotlin 中对列表排序可以直接调用 sorted() 或 sortedDescending() 函数，而在 Java 中需要更多的样板代码。

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;
    }

    public String getName() {
        return name;
    }
}

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

        Collections.sort(people, new Comparator<Person>() {
            @Override
            public int compare(Person p1, Person p2) {
                return p1.getAge() - p2.getAge();
            }
        });

        for (Person person : people) {
            System.out.println("Name: " + person.getName() + ", Age: " + person.getAge());
        }
    }
}

对比 Kotlin 代码：

data class Person(val name: String, val age: Int) : Comparable<Person> {
    override fun compareTo(other: Person): Int {
        return this.age - other.age
    }
}

fun main() {
    val people = listOf(
        Person("Alice", 30),
        Person("Bob", 25),
        Person("Charlie", 35)
    )
    val sortedPeople = people.sorted()
    sortedPeople.forEach { println("Name: ${it.name}, Age: ${it.age}") }
}

可以看到，Kotlin 代码更简洁，特别是在定义比较逻辑和调用排序方法方面。

分组

在 Java 中，分组通常需要使用 Collectors.groupingBy 方法结合流（Stream API）来实现。

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

class Fruit {
    private String name;
    private String color;

    public Fruit(String name, String color) {
        this.name = name;
        this.color = color;
    }

    public String getColor() {
        return color;
    }

    public String getName() {
        return name;
    }
}

public class Main {
    public static void main(String[] args) {
        List<Fruit> fruits = new ArrayList<>();
        fruits.add(new Fruit("Apple", "Red"));
        fruits.add(new Fruit("Banana", "Yellow"));
        fruits.add(new Fruit("Cherry", "Red"));
        fruits.add(new Fruit("Lemon", "Yellow"));

        Map<String, List<Fruit>> groupedFruits = fruits.stream()
               .collect(Collectors.groupingBy(Fruit::getColor));

        groupedFruits.forEach((color, fruitsInColor) -> {
            System.out.println("Color: " + color);
            fruitsInColor.forEach(fruit -> System.out.println(" - " + fruit.getName()));
        });
    }
}

而 Kotlin 中使用 groupBy 函数更加直观和简洁。

data class Fruit(val name: String, val color: String)

fun main() {
    val fruits = listOf(
        Fruit("Apple", "Red"),
        Fruit("Banana", "Yellow"),
        Fruit("Cherry", "Red"),
        Fruit("Lemon", "Yellow")
    )
    val groupedFruits = fruits.groupBy { it.color }
    groupedFruits.forEach { (color, fruitsInColor) ->
        println("Color: $color")
        fruitsInColor.forEach { println(" - ${it.name}") }
    }
}

Kotlin 的 groupBy 函数直接在集合上调用，语法更紧凑，不需要像 Java 那样使用流 API 和 Collectors 类。

总结

Kotlin 的集合排序和分组功能为开发者提供了强大且灵活的数据处理能力。通过 sorted、sortedDescending 等排序函数以及 groupBy 分组函数，我们可以轻松地对各种类型的集合进行排序和分组操作。无论是基本类型集合还是自定义对象集合，无论是简单的排序和分组需求还是复杂的多字段排序和多级分组需求，Kotlin 都能很好地满足。同时，在使用过程中要注意性能问题，特别是在处理大规模集合时。与 Java 相比，Kotlin 在集合排序和分组方面的语法更加简洁，使用起来更加方便。熟练掌握这些功能，可以提高我们在 Kotlin 编程中的效率和代码质量。