Zig中如何无需分配器实现返回新数组的冒泡排序？

目标与遇到的问题 #

我希望在Zig中实现冒泡排序，让函数返回一个新数组，这样能更方便地编写简洁的单行测试。但直接尝试创建动态长度的栈数组时遇到了问题：

pub fn bubbleSort(arr: []const u8,) []const u8 {
    var arrSorted = [_]u8{0} ** arr.len;
    std.mem.copyForwards(u8, &arrSorted, arr);
    ...
}

Zig会报错，因为arr.len不是编译期已知的常量，栈数组的长度必须在编译期确定。

当前实现方案 #

我最终通过传入编译期已知的长度参数解决了问题，代码如下：

const std = @import("std");

/// O(n^2)
pub fn bubbleSort(arr: []const u8, comptime len: u8) []const u8 {
    var arrSorted = [_]u8{0} ** len;
    std.mem.copyForwards(u8, &arrSorted, arr);

    for (0..arrSorted.len) |i| {
        for (0..arrSorted.len - i - 1) |j| {
            if (arrSorted[j] > arrSorted[j + 1]) {
                const tmp = arrSorted[j];
                arrSorted[j] = arrSorted[j + 1];
                arrSorted[j + 1] = tmp;
            }
        }
    }

    return &arrSorted;
}

test "bubble sort" {
    try std.testing.expectEqualSlices(u8, &[_]u8{ 1, 4, 7, 8, 9, 102 }, bubbleSort(&[_]u8{ 1, 102, 7, 4, 8, 9 }, 6));
    try std.testing.expectEqualSlices(u8, &[_]u8{ 1, 4, 7, 8, 9, 102 }, bubbleSort(&[_]u8{ 102, 7, 4, 1, 8, 9 }, 6));
    try std.testing.expectEqualSlices(u8, &[_]u8{ 1, 4, 7, 8, 9, 102 }, bubbleSort(&[_]u8{ 1, 102, 7, 4, 9, 8 }, 6));
    try std.testing.expectEqualSlices(u8, &[_]u8{ 1, 4, 7, 8, 9, 102 }, bubbleSort(&[_]u8{ 9, 1, 102, 7, 4, 8 }, 6));
    try std.testing.expectEqualSlices(u8, &[_]u8{ 1, 4, 7, 8, 9, 102 }, bubbleSort(&[_]u8{ 1, 7, 4, 8, 9, 102 }, 6));
}

通过将数组长度作为编译期参数传入，让len成为编译期已知量，从而能创建对应长度的栈数组并返回其切片。

疑问解答 #

传入allocator是否是正确方式？ #

是的，传入allocator是Zig中实现这类通用场景的标准正确做法。当数组长度只有运行时才能确定时，栈上无法创建动态长度的数组（Zig要求栈数组长度必须是编译期常量），此时必须通过堆分配来创建新数组。

基于allocator的实现示例 #

const std = @import("std");

pub fn bubbleSort(allocator: std.mem.Allocator, arr: []const u8) ![]u8 {
    // 分配与原数组长度相同的内存
    var arrSorted = try allocator.alloc(u8, arr.len);
    // 确保后续出错时自动释放已分配的内存
    errdefer allocator.free(arrSorted);
    
    std.mem.copyForwards(u8, arrSorted, arr);

    for (0..arrSorted.len) |i| {
        for (0..arrSorted.len - i - 1) |j| {
            if (arrSorted[j] > arrSorted[j + 1]) {
                // 用std.mem.swap简化交换逻辑
                std.mem.swap(u8, &arrSorted[j], &arrSorted[j + 1]);
            }
        }
    }

    return arrSorted;
}

test "bubble sort with allocator" {
    const allocator = std.testing.allocator;
    try std.testing.expectEqualSlices(u8, &[_]u8{1, 4, 7, 8, 9, 102}, try bubbleSort(allocator, &[_]u8{1, 102, 7, 4, 8, 9}));
    try std.testing.expectEqualSlices(u8, &[_]u8{1, 4, 7, 8, 9, 102}, try bubbleSort(allocator, &[_]u8{102, 7, 4, 1, 8, 9}));
    try std.testing.expectEqualSlices(u8, &[_]u8{1, 4, 7, 8, 9, 102}, try bubbleSort(allocator, &[_]u8{1, 102, 7, 4, 9, 8}));
}

不同方案的对比 #

• 编译期长度参数方案：仅适用于数组长度在编译期已知的场景，优势是不需要堆分配，性能略高，但通用性差，调用者必须手动传入长度常量。
• allocator方案：支持运行时动态长度的数组，适用性更广，符合Zig的内存管理规范（明确内存所有权，由调用者负责释放内存），是通用场景下的最优解。

关于无需allocator和编译期参数返回新数组的可能性 #

Zig中无法实现这一点：函数返回的栈数组在函数执行结束后会随栈帧被销毁，返回的指针会变成悬垂指针，属于不安全行为，因此Zig不允许这样做。必须在栈上用编译期固定长度数组，或在堆上用allocator分配内存。

内容的提问来源于stack exchange，提问作者Arakan