Day 28: std.sort模块：排序算法

1. 引言

欢迎来到第二十八天！排序是计算机科学中最基本、最常见的任务之一。std.sort 模块为Zig程序员提供了一套高效、灵活且类型安全的排序工具。与 std.math 类似，std.sort 中的函数也是泛型的，可以对任何类型的切片进行排序，只要你能为该类型定义一个“小于”关系。今天，我们将学习如何使用 std.sort.sort 函数，如何提供自定义的比较逻辑，以及何时可能需要使用标准库提供的其他特定排序算法。

2. std.sort.sort

最核心的排序函数是 std.sort.sort。它接受三个参数：

• T: type: 要排序的元素的类型。
• slice: []T: 要进行原地排序的切片。
• context: anytype: 一个传递给比较函数的上下文对象，通常是 {} (一个空的匿名结构体) 如果不需要额外上下文。
• lessThan: fn(context: anytype, a: T, b: T) bool: 一个比较函数，当 a应该排在b前面时，它返回 true。

const std = @import("std");

// 自定义比较函数
fn i32LessThan(context: void, a: i32, b: i32) bool {
    _ = context; // 明确表示我们不使用context
    return a < b;
}

pub fn main() !void {
    var numbers = [_]i32{ 5, 2, 8, 1, 9 };

    std.sort.sort(i32, &numbers, {}, i32LessThan);

    std.debug.print("{any}\n", .{numbers}); // { 1, 2, 5, 8, 9 }
}

sort 函数会原地修改切片，它不返回任何值。它使用的排序算法是经过优化的内省排序（Introsort），在大多数情况下都有很好的性能表现（平均时间复杂度为 O(n log n)）。

3. 自定义比较器

sort 函数的强大之处在于你可以提供任意的比较逻辑。例如，我们可以对一个结构体切片按照某个特定字段进行排序。

const User = struct { name: []const u8, age: u32 };

// 按年龄升序排序
fn userAgeLessThan(context: void, a: User, b: User) bool {
    _ = context;
    return a.age < b.age;
}

var users = [_]User{
    .{ .name = "Alice", .age = 30 },
    .{ .name = "Bob", .age = 25 },
    .{ .name = "Charlie", .age = 35 },
};

std.sort.sort(User, &users, {}, userAgeLessThan);
// 排序后: Bob, Alice, Charlie

4. 稳定排序 (Stable Sort)

std.sort.sort 使用的内省排序是不稳定的。这意味着如果两个元素的比较结果是相等（即 lessThan(a, b) 和 lessThan(b, a) 都返回 false），它们在排序后的相对顺序是不保证的。

在某些场景下，保持相等元素的原始顺序很重要。这时，你需要使用稳定排序算法。std.sort 提供了 insertionSort 和 mergeSort，它们都是稳定的。

• insertionSort: 对于小切片或者大部分已经排好序的切片，它的性能非常好。std.sort.sort 内部在处理小分区时就会切换到插入排序。
• mergeSort: 归并排序。它需要额外的内存分配来辅助排序，因此你需要提供一个分配器。

// 假设我们先按姓氏排序，再按年龄排序（稳定）
// std.sort.mergeSort(User, &users, {}, userLastNameLessThan, allocator);
// std.sort.mergeSort(User, &users, {}, userAgeLessThan, allocator);

5. 示例：多键排序

如果需要根据多个字段进行排序，可以在比较函数中实现这个逻辑。

// 先按年龄降序，如果年龄相同，再按名字升序
fn customUserSort(context: void, a: User, b: User) bool {
    _ = context;
    if (a.age != b.age) {
        return a.age > b.age; // 年龄降序
    }
    // 年龄相同，比较名字
    return std.mem.order(u8, a.name, b.name) == .lt; // 名字升序
}

std.sort.sort(User, &users, {}, customUserSort);

6. 实践练习：实现你自己的快速排序

这是一个经典的算法练习。尝试实现你自己的 quickSort 函数。

1. 函数签名应该是 fn quickSort(T: type, slice: []T, lessThan: fn(T, T) bool) void。
2. 选择一个基准（pivot）元素。
3. 将切片分区，使得所有小于基准的元素都在它前面，所有大于的都在它后面。
4. 递归地对基准前后的两个子切片进行排序。

这个练习将加深你对排序算法、切片和泛型编程的理解。

7. 常见问题

问：为什么 sort 需要 T 作为一个显式参数？

答：因为 slice 参数的类型是 []T，编译器可以从中推断出 T。但在Zig的早期版本中，类型推断能力有限，需要显式传递。虽然现在在很多情况下可以省略，但保留它是一种清晰且向后兼容的做法。在更复杂的泛型场景中，显式传递类型仍然是必要的。

问：std.sort 和 std.mem.order 有什么关系？

答：std.mem.order 是进行字典序比较的基础工具。许多 lessThan 函数的最终实现都会调用 std.mem.order 来比较字符串或字节切片，如我们在多键排序示例中看到的那样。

8. binarySearch

一旦一个切片被排序，你就可以使用 std.sort.binarySearch 来非常高效地（O(log n) 时间复杂度）查找一个元素。它返回找到的元素的索引，如果找不到，则返回 null。

const sorted_numbers = [_]i32{ 1, 2, 5, 8, 9 };
const index = std.sort.binarySearch(i32, &sorted_numbers, 8, {}, i32LessThan);
// index 是一个 ?usize，值为 3

9. 总结

今天，我们学习了如何使用 std.sort 模块来为我们的数据排序。我们掌握了核心的 sort 函数，并理解了通过自定义比较函数来处理复杂排序逻辑的强大能力。我们还区分了稳定排序和不稳定排序，并了解了 binarySearch 在已排序数据上的高效性。排序是算法的基石，Zig标准库为此提供了强大、灵活且类型安全的工具。

明天，我们将学习 std.hash 模块，探索如何为数据生成哈希值，这是构建 HashMap 等数据结构的关键。