Zig 语言实战：实现高性能快速排序算法

在上一篇博客中，我们深入探讨了如何在 Rust 中利用OrdTrait 和checked_sub来实现一个安全的快速排序。今天，我们将视角转向Zig 语言。

Zig 被设计为 C 语言的现代替代品，它没有隐藏的控制流，内存管理完全由开发者掌控。在实现快速排序时，Zig 的代码往往更加直观，性能也通常与 C 语言持平。

本文将带你手写一个包含三数取中优化的快速排序，体验 Zig 简洁而强大的语法特性。

算法核心思路

快速排序的核心依然是分治法（Divide and Conquer）：

1. 选取基准（Pivot）：从数组中挑出一个元素，这里我们使用“三数取中法”来避免最坏情况。
2. 分区（Partition）：将比基准小的元素移到左边，比基准大的移到右边。
3. 递归（Recursion）：对左右两个子数组递归执行上述步骤。

Zig 的实现与 Rust 的主要区别在于：

• 泛型：使用comptime T而非 Trait Bounds。
• 交换：直接使用标准库的mem.swap或内置函数。
• 边界：Zig 的usize下溢行为是截断（Truncate），而非 Panic，所以我们需要更小心，或者利用切片的特性。

完整代码实现

以下是完整的 Zig 快速排序实现。你可以直接将这段代码保存为quick_sort.zig并运行测试。

conststd=@import("std");constmem=std.mem;/// 快速排序主函数////// # 参数/// - `arr`: 需要排序的切片引用////// # 示例/// ```/// var arr = [_]i32{ 3, 1, 4, 1, 5 };/// try quickSort(&arr);/// std.debug.print("{any}\n", .{arr}); // 输出: { 1, 1, 3, 4, 5 }/// ```pubfnquickSort(comptimeT:type,arr:[]T)void{if(arr.len<=1)return;quickSortImpl(T,arr,0,arr.len-1);}/// 快速排序递归实现fnquickSortImpl(comptimeT:type,arr:[]T,left:usize,right:usize)void{// 递归终止条件if(left>=right){return;}// 分区并获取基准位置constpivot=partition(T,arr,left,right);// 递归排序左侧 [left, pivot-1]// 注意：Zig 中 usize 下溢会回绕，需手动保护if(pivot>0){quickSortImpl(T,arr,left,pivot-1);}// 递归排序右侧 [pivot+1, right]// 当 pivot == right 时，pivot + 1 可能越界，但递归函数开头会拦截quickSortImpl(T,arr,pivot+1,right);}/// 三数取中法选择基准索引fnmedianOfThree(comptimeT:type,arr:[]T,left:usize,right:usize)usize{constmid=left+(right-left)/2;// 将 left, mid, right 三个位置的元素按大小排序，确保 arr[mid] 是中位数if(arr[left]>arr[mid]){mem.swap(T,&arr[left],&arr[mid]);}if(arr[left]>arr[right]){mem.swap(T,&arr[left],&arr[right]);}if(arr[mid]>arr[right]){mem.swap(T,&arr[mid],&arr[right]);}returnmid;}/// 分区函数 (Hoare Partition)fnpartition(comptimeT:type,arr:[]T,left:usize,right:usize)usize{// 1. 使用三数取中，并将中位数交换到 left 位置作为基准constmid_index=medianOfThree(T,arr,left,right);mem.swap(T,&arr[left],&arr[mid_index]);// 2. 初始化双指针var i=left+1;var j=right;while(true){// 从左找 >= 基准的元素while(i<=j and arr[i]<arr[left]):(i+=1){}// 从右找 <= 基准的元素while(i<=j and arr[j]>arr[left]):(j-=1){}// 指针相遇，退出if(i>=j)break;// 交换逆序对mem.swap(T,&arr[i],&arr[j]);i+=1;j-=1;}// 3. 将基准放到正确的位置 (j)mem.swap(T,&arr[left],&arr[j]);returnj;}// ================== 测试代码 ==================test"quick sort"{constexpect=@import("std").testing.expect;var arr=[_]i32{3,1,4,1,5,9,2,6};quickSort(i32,&arr);tryexpect(mem.eql(i32,&arr,&[_]i32{1,1,2,3,4,5,6,9}));}// 编译并运行测试: `zig test quick_sort.zig`

核心代码解析

1. 泛型的写法：comptime T

与 Rust 的T: Ord不同，Zig 使用comptime T（编译时类型）。Zig 的泛型是在编译时展开的，这意味着quickSort(i32, ...)和quickSort(f64, ...)会被编译器生成两份完全独立的代码。这种方式没有运行时多态的开销，性能极高。

2. 内存交换：mem.swap

Zig 标准库提供了std.mem.swap，它利用了@ptrCast和@sizeOf来实现类型安全的内存交换。这比 Rust 的Clone更高效，因为它直接操作内存，不涉及构造函数或析构函数。

3. 边界安全：usize下溢

这是 Zig 和 Rust 最大的区别之一：

• Rust：0usize - 1在 Debug 模式下会 Panic，保护了程序。
• Zig：0 - 1的结果是std.math.maxInt(usize)（一个极大值）。这虽然快，但极其危险。
• 我们的处理：在递归调用左侧前，我们显式地加了if (pivot > 0)判断。这是一种显式的防御性编程，符合 Zig 的设计哲学——“显式优于隐式”。

4. 三数取中优化

我们在medianOfThree函数中，不仅计算了中位数的索引，还直接通过交换把这三个数排好了序（arr[left] <= arr[mid] <= arr[right]），然后直接返回mid。这使得基准值的质量更高，提升了整体排序效率。

️ Rust vs Zig：思维转换

如果你刚从 Rust 转向 Zig，以下几点值得注意：

总结

通过这个例子，我们可以看到 Zig 语言的简洁与高效。它没有隐藏的运行时机制，所有的操作都是你明确写出的。

虽然在处理usize下溢时需要比 Rust 多一份小心，但换来的是对内存布局和执行流程的绝对控制权。对于系统编程、嵌入式开发或者对性能有极致要求的算法场景，Zig 是一个非常值得考虑的选择。

小贴士：在实际的 Zig 项目中，你可以直接使用标准库的std.sort.sort，它已经实现了 IntroSort（内省排序），性能非常强悍。手写此算法主要用于学习算法原理和熟悉语言特性。