You need to enable JavaScript to run this app. C++运行时定尺寸无全局变量时3D数组传参与按a[x][0][0]排序实现
优惠活动
大模型
产品
解决方案
定价
更多

C++运行时定尺寸无全局变量时3D数组传参与按a[x][0][0]排序实现

运行时定尺寸三维数组的函数传参与快速排序实现

原代码存在的核心问题

  • 采用非C++标准的变长数组(VLA)语法int a[size][size][size],仅GCC、Clang等编译器作为扩展支持,MSVC等环境下无法编译,且栈上分配大尺寸数组易触发栈溢出。
  • 函数参数签名与实际数组类型不匹配:partition中声明的int *a[size][size]依赖不存在的编译期size常量,quick_sort将三维数组误声明为单int*类型,无法正确索引数组元素。
  • 排序逻辑存在错误:分区循环中将r--误写为r++,会触发无限循环、内存越界;主函数中未定义左边界变量l就传入排序函数,触发未定义行为。
  • 本质上的限制:C++中静态多维数组作为函数参数时,除第一维外的所有维度必须是编译期常量,这也是此前所有参考实现都要求预设const尺寸的根本原因。

可落地的无编译期常量要求的实现方案

方案1:使用std::vector作为动态三维容器(最推荐)

std::vector的尺寸完全由运行时输入决定,不需要任何编译期常量,且自动管理内存,无栈溢出风险,全程不依赖全局变量。
实现代码:

#include <vector>
#include <utility> // for std::swap

// 直接传入三维vector的引用,无需额外传递尺寸
int partition(std::vector<std::vector<std::vector<int>>>& a, int l, int r) {
    int pivot_val = a[l][0][0];
    int pivot_pos = l;
    while (l < r) {
        // 修正原逻辑的遍历方向错误
        while (l < r && a[r][0][0] >= pivot_val) r--;
        while (l < r && a[l][0][0] <= pivot_val) l++;
        if (l < r) {
            // 按需求仅交换[x][0][0]位置的元素
            std::swap(a[l][0][0], a[r][0][0]);
        }
    }
    std::swap(a[pivot_pos][0][0], a[r][0][0]);
    return r;
}

void quick_sort(std::vector<std::vector<std::vector<int>>>& a, int l, int r) {
    if (l < r) {
        int pivot = partition(a, l, r);
        quick_sort(a, l, pivot - 1);
        quick_sort(a, pivot + 1, r);
    }
}

int main() {
    int size;
    std::cin >> size;
    // 运行时根据输入size构造三维数组,无需编译期常量
    std::vector<std::vector<std::vector<int>>> a(
        size, 
        std::vector<std::vector<int>>(size, std::vector<int>(size))
    );
    // 补上原代码缺失的初始左边界定义
    quick_sort(a, 0, size - 1);
}

方案2:连续动态内存块(零额外开销)

如果需要原生数组的低开销性能,可将三维数组的所有元素存储在一块连续的动态内存中,通过显式传入的维度尺寸计算元素偏移,绕开静态数组的编译期维度限制。
3D数组元素a[x][y][z]的内存偏移计算公式为:x * size * size + y * size + z,排序时仅需访问[x][0][0]位置,对应偏移为x * size * size。
实现代码:

#include <utility> // for std::swap

// 传参:内存首地址,维度尺寸,排序左右边界
int partition(int* a, int size, int l, int r) {
    // 封装[x][0][0]元素的访问逻辑
    auto get_element = [&](int x) { return a[x * size * size]; };
    int pivot_val = get_element(l);
    int pivot_pos = l;
    while (l < r) {
        while (l < r && get_element(r) >= pivot_val) r--;
        while (l < r && get_element(l) <= pivot_val) l++;
        if (l < r) {
            std::swap(get_element(l), get_element(r));
        }
    }
    std::swap(get_element(pivot_pos), get_element(r));
    return r;
}

void quick_sort(int* a, int size, int l, int r) {
    if (l < r) {
        int pivot = partition(a, size, l, r);
        quick_sort(a, size, l, pivot - 1);
        quick_sort(a, size, pivot + 1, r);
    }
}

int main() {
    int size;
    std::cin >> size;
    // 动态申请连续内存,不会触发栈溢出
    int* a = new int[size * size * size];
    quick_sort(a, size, 0, size - 1);
    // 手动释放内存
    delete[] a;
}

适配扩展说明

如果排序需求调整为:排序时连带交换整个x对应的二维块,而非仅交换[x][0][0]位置的单元素,仅需将代码中交换单元素的逻辑,替换为交换对应位置的二维块即可,不需要修改参数传递的整体逻辑。


内容的提问来源于stack exchange,提问作者ธีรพัฒน์ หงส์วรพิพัฒน์

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.08 21:06:03